読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2767

contest contest-codeIQ language language-c++11

説明が不十分だと思うのだけど, 同じ類似度の時にインデックスの小さい方を先に出さないとtest case2で落ちる.

int tn;
vector<int> ns;
vector<int> tmp;

int norm(vector<int> v)
{
  int ans = 0;
  int until = v.size()-1;
  FOR(i,1,until) ans+=v[i]*v[i];
  return ans;
}

int dot(vector<int> u, vector<int> v)
{
  int ans = 0;
  int until = min(u.size(),v.size())-1;
  FOR(i,1,until) ans += u[i]*v[i];
  return ans*ans;
}

bool cmp(vector<int> u, vector<int> v)
{
  int un = dot(u,tmp);
  int ud = tn*ns[u[0]];
  int vn = dot(v,tmp);
  int vd = tn*ns[v[0]];
  double a = 1.0*un/ud;
  double b = 1.0*vn/vd;
  return (un*vd==vn*ud)?u[0]<v[0]:a>b;
}

void solve(vector<vector<int>> T,int id)
{
  tmp = T[id];
  tn = ns[id];
  sort(T.begin()+1,T.end(),cmp);
  printf("%d ",id);
  FOR(i,2,4) printf("%d%s",T[i][0],i==4?"\n":" ");
}

int main()
{
  int nu, ni, n; scanf("%d %d %d",&nu, &ni, &n);
  vector<vector<int> > T(ni+1,vector<int>(nu+1,0));
  FOR(i,1,ni) T[i][0] = i;
  REP(i,n)
  {
    int item, user, rate;
    scanf("%d %d %d",&user, &item, &rate);
    T[item][user] = rate;
  }
  //FOR(i,1,ni){ FOR(j,1,nu) cout << T[i][j]; cout << endl;}
  ns.resize(ni+1);
  FOR(i,1,ni) ns[i] = norm(T[i]);
  int m; scanf("%d",&m);
  REP(i,m)
  {
    int item; scanf("%d",&item);
    solve(T,item);
  }
  return 0;
}