#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}];
}
bool pyt(int a, int b) {
if(abs(a-b)==1) return a<b;
return 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>rev(vector<int>T) {
int n=T.size();
rep(i, n) {
int x=n;
for(int j=i+2; j<n; ++j) {
if(query(T[j-2], T[j])==false) {
x=j;
break;
}
}
reverse(T.begin()+i, T.begin()+x);
i=x-1;
}
return T;
}
bool check(vector<int>T, vector<int>P) {
rep(i, T.size()-2) if(query(T[i], T[i+2])!=pyt(P[T[i]], P[T[i+2]])) return false;
return true;
}
vector<int>Solve(int n) {
vector<int>T(n);
rep(i, n) T[i]=i;
T=cd(T);
vector<int>A, B, C, D;
rep(i, n-1) A.pb(T[i+1]);
rep(i, n-1) B.pb(T[i]);
rep(i, n-2) C.pb(T[i+1]);
rep(i, n) D.pb(T[i]);
A=rev(A);
B=rev(B);
C=rev(C);
D=rev(D);
vector<int>Ap(n), Bp(n), Cp(n), Dp(n);
rep(i, n-1) Ap[A[i]]=i+1;
rep(i, n-1) Bp[B[i]]=i;
Bp[T[n-1]]=n-1;
rep(i, n-2) Cp[C[i]]=i+1;
Cp[T[n-1]]=n-1;
rep(i, n) Dp[D[i]]=i;
if(check(T, Ap)) return Ap;
if(check(T, Bp)) return Bp;
if(check(T, Cp)) return Cp;
return Dp;
}
Compilation message
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:28:3: note: in expansion of macro 'rep'
28 | rep(i, T.size()/2) A.pb(T[i]);
| ^~~
monster.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=T.size()/2; i<T.size(); ++i) B.pb(T[i]);
| ~^~~~~~~~~
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() && l2<B.size()) {
| ~~^~~~~~~~~
monster.cpp:34:26: 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() && l2<B.size()) {
| ~~^~~~~~~~~
monster.cpp:38:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while(l1<A.size()) P.pb(A[l1++]);
| ~~^~~~~~~~~
monster.cpp:39:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(l2<B.size()) P.pb(B[l2++]);
| ~~^~~~~~~~~
monster.cpp: In function 'bool check(std::vector<int>, 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:58:3: note: in expansion of macro 'rep'
58 | rep(i, T.size()-2) if(query(T[i], T[i+2])!=pyt(P[T[i]], P[T[i+2]])) return false;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [3] |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [3] |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
1364 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
