Submission #1030948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030948		AdamGS	Monster Game (JOI21_monster)	C++17	100 / 100	55 ms	600 KiB

monster

#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
map<pair<int,int>,int>mp;
bool query(int a, int b) {
  return Query(a, b);
  if(mp.find({a, b})!=mp.end()) return mp[{a, b}];
  if(Query(a, b)) {
    mp[{a, b}]=1;
    mp[{b, a}]=0;
  } else {
    mp[{b, a}]=1;
    mp[{a, b}]=0;
  }
  return mp[{a, b}];
}
vector<int>cd(vector<int>T) {
  if(T.size()==1) return T;
  vector<int>A, B;
  rep(i, T.size()/2) A.pb(T[i]);
  for(int i=T.size()/2; i<T.size(); ++i) B.pb(T[i]);
  A=cd(A);
  B=cd(B);
  int l1=0, l2=0;
  vector<int>P;
  while(l1<A.size() && l2<B.size()) {
    if(query(A[l1], B[l2])==false) P.pb(A[l1++]);
    else P.pb(B[l2++]);
  }
  while(l1<A.size()) P.pb(A[l1++]);
  while(l2<B.size()) P.pb(B[l2++]);
  return P;
}
vector<int>Solve(int n) {
  vector<int>T(n);
  rep(i, n) T[i]=i;
  T=cd(T);
  string s="";
  if(query(T[0], T[2])) s+="1"; else s+="0";
  if(query(T[0], T[3])) s+="1"; else s+="0";
  if(query(T[1], T[3])) s+="1"; else s+="0";
  int l=0;
  if(s=="001" || s=="011" || s=="101") {
    l=1;
  } else if(s=="000" || s=="010") {
    reverse(T.begin(), T.begin()+2);
    l=2;
  } else if(s=="110") {
    reverse(T.begin(), T.begin()+3);
    l=3;
  } else if(s=="111") {
    l=4;
    while(l<n) {
      if(query(T[l-2], T[l])==false) break;
      ++l;
    }
    reverse(T.begin(), T.begin()+l);
  } else {
    l=4;
    while(l<n) {
      if(query(T[0], T[l])==true) {
        swap(T[0], T[2]);
        break;
      }
      if(query(T[1], T[l])==true) {
        swap(T[1], T[2]);
        break;
      }
      if(query(T[2], T[l])==true) {
        swap(T[0], T[1]);
        break;
      }
      ++l;
    }
    ++l;
    reverse(T.begin()+3, T.begin()+l);
  }
  while(l<n) {
    int p=l;
    while(query(T[l-1], T[p])==false) ++p;
    reverse(T.begin()+l, T.begin()+p+1);
    l=p+1;
  }
  vector<int>P(n);
  rep(i, n) P[T[i]]=i;
  return P;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> cd(std::vector<int>)':
monster.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
monster.cpp:25:3: note: in expansion of macro 'rep'
   25 |   rep(i, T.size()/2) A.pb(T[i]);
      |   ^~~
monster.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=T.size()/2; i<T.size(); ++i) B.pb(T[i]);
      |                         ~^~~~~~~~~
monster.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(l1<A.size() && l2<B.size()) {
      |         ~~^~~~~~~~~
monster.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(l1<A.size() && l2<B.size()) {
      |                        ~~^~~~~~~~~
monster.cpp:35:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   while(l1<A.size()) P.pb(A[l1++]);
      |         ~~^~~~~~~~~
monster.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while(l2<B.size()) P.pb(B[l2++]);
      |         ~~^~~~~~~~~

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