Submission #1053918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053918		Itamar	Monster Game (JOI21_monster)	C++17	91 / 100	62 ms	672 KiB

monster

#include<vector>
using namespace std;
#define vi vector<int>

bool Query(int a, int b);

void sorti(vi &v){
  vi v1,v2;
  int s = v.size();
  if(s==1)return;
  for(int i = 0; i <s/2; i++ )v1.push_back(v[i]);
  for(int i = s/2; i < s; i++)v2.push_back(v[i]);
  sorti(v1);
  sorti(v2);
  vi vt;
  int it = 0;
  for(int i= 0; i < s/2; i++){
    while(it < v2.size() && !Query(v2[it],v1[i])){
      vt.push_back(v2[it]);
      it++;
    }vt.push_back(v1[i]);
  }
  while(it < v2.size()){
      vt.push_back(v2[it]);
      it++;
    }
    v=vt;
}
int n;
int find(int ind){
  int sum = 0;
  vi win,lose;
  for(int i = 0; i < n; i++){
    if(ind == i)continue;
    if(Query(ind,i))win.push_back(i);
    else lose.push_back(i);
  }
  if(win.size()==1){
    int sum = 0;
    for(int i = 0; i < n; i++){
      if(i!=win[0]){
        sum += Query(win[0],i);
            if(sum == 2)return 1;
      }
    }
     return 0;
  }else if(lose.size() == 1){
    int sum = 0;
    for(int i = 0; i < n; i++){
      if(i!=lose[0]){
        sum += Query(i,lose[0]);
            if(sum == 2)return n-2;
      }
    }
     return n-1;
  }else{
    return win.size();
  }
}
std::vector<int> Solve(int N) {
  n=N;
  std::vector<int> ans;
  vi v; for(int i = 0; i <N; i++)v.push_back(i);
  sorti(v);
  vi res(N);
  int l = 0,r = find(v[0]);
  for(int i = r; i>=0; i--)ans.push_back(i);
  while(ans.size()<N){
    int lt = r+1;
    for(int i = lt; i < N; i++){
      if(Query(v[l],v[i])){
        l = lt;
        r = i;
        for(int j = r; j>=l; j--)ans.push_back(j);
        break;
      }
    }
  }
  for(int i = 0; i < N; i++){
    res[v[i]] = ans[i];
  }
  return res;
}

Compilation message (stderr)

monster.cpp: In function 'void sorti(std::vector<int>&)':
monster.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     while(it < v2.size() && !Query(v2[it],v1[i])){
      |           ~~~^~~~~~~~~~~
monster.cpp:23:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   while(it < v2.size()){
      |         ~~~^~~~~~~~~~~
monster.cpp: In function 'int find(int)':
monster.cpp:31:7: warning: unused variable 'sum' [-Wunused-variable]
   31 |   int sum = 0;
      |       ^~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:68:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   while(ans.size()<N){
      |         ~~~~~~~~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 66 / 75