This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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) {
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:24:3: note: in expansion of macro 'rep'
24 | rep(i, T.size()/2) A.pb(T[i]);
| ^~~
monster.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=T.size()/2; i<T.size(); ++i) B.pb(T[i]);
| ~^~~~~~~~~
monster.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | while(l1<A.size() && l2<B.size()) {
| ~~^~~~~~~~~
monster.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | while(l1<A.size() && l2<B.size()) {
| ~~^~~~~~~~~
monster.cpp:34:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(l1<A.size()) P.pb(A[l1++]);
| ~~^~~~~~~~~
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(l2<B.size()) P.pb(B[l2++]);
| ~~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |