#include "monster.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) return cout<<x<<"\n", 0;
#define SZ(x) ((int)x.size())
const int inf=1000010000;
const int mod=1000000007;
const int MAXN=1010;
int n, m, q, k, u, v, x, y, t, l, r, ans;
int A[MAXN][MAXN];
int P[MAXN], deg[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool Ask(int u, int v){
if (u==v) return 0; // wtf
if (u>v) return !Ask(v, u);
if (A[u][v]==-1) A[u][v]=!Query(u, v);
return A[u][v];
}
vi FUCK(vi A){
vi B(n, 0);
for (int i=0; i<n; i++) B[A[i]]=i;
return B;
}
void MergeSort(int *l, int *r){
if (r-l<=1) return ;
int *mid=(r-l)/2+l;
MergeSort(l, mid);
MergeSort(mid, r);
vector<int> vec(r-l, 0);
merge(l, mid, mid, r, vec.begin(), Ask);
for (int i=0; i<r-l; i++) (*(l+i))=vec[i];
}
vi Solve(int _n){
n=_n;
memset(A, -1, sizeof(A));
vi out;
iota(P, P+n, 0);
shuffle(P, P+n, rng);
MergeSort(P, P+n);
// cerr<<"P: ";for (int i=0; i<n; i++) cerr<<P[i]<<" \n"[i==n-1];
int t=0, y=P[n-1];
for (int i=0; i<n; i++) if (i!=y) t+=Ask(y, i);
if (t==n-2){
if (Ask(P[2], P[0])){
for (int i=n-1; ~i; i--) out.pb(P[i]);
}
else{
out.pb(P[0]);
for (int i=n-1; i; i--) out.pb(P[i]);
}
// debugv(out)
// debug("shit")
return FUCK(out);
}
int j=0, pos=n-1;
for (int i=0; i<n-1; i++) if (Ask(y, P[i])){
x=P[i];
j=i;
break ;
}
if (t==1){
int tx=0;
for (int i=n-1; ~i && tx<=1; i--) if (P[i]!=x) tx+=Ask(x, P[i]);
if (tx==1){
out.pb(P[pos--]);
}
else{
out.pb(P[pos--]);
out.pb(P[pos--]);
assert(tx<n-2);
}
}
else{
out.pb(P[pos--]);
out.pb(P[pos--]);
while (~pos && P[pos]!=x && Ask(y, P[pos])) out.pb(P[pos--]);
}
reverse(all(out));
// debugv(out)
int last=P[n-1];
while (~pos){
int nw=P[pos];
vi shit;
while (1){
int v=P[pos--];
shit.pb(v);
if (Ask(last, v)) break ;
}
reverse(all(shit));
for (int x:shit) out.pb(x);
last=nw;
}
reverse(all(out));
return FUCK(out);
}
Compilation message
monster.cpp: In function 'vi Solve(int)':
monster.cpp:74:6: warning: variable 'j' set but not used [-Wunused-but-set-variable]
74 | int j=0, pos=n-1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4296 KB |
Output is correct |
| 2 |
Runtime error |
6 ms |
8520 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4296 KB |
Output is correct |
| 2 |
Runtime error |
6 ms |
8520 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
120 ms |
4296 KB |
Partially correct |
| 2 |
Partially correct |
92 ms |
4404 KB |
Partially correct |
| 3 |
Partially correct |
128 ms |
4296 KB |
Partially correct |
| 4 |
Partially correct |
110 ms |
4280 KB |
Partially correct |
| 5 |
Partially correct |
126 ms |
4296 KB |
Partially correct |
| 6 |
Correct |
109 ms |
4288 KB |
Output is correct |
| 7 |
Correct |
115 ms |
4296 KB |
Output is correct |
| 8 |
Partially correct |
106 ms |
4296 KB |
Partially correct |
| 9 |
Partially correct |
114 ms |
4288 KB |
Partially correct |
| 10 |
Partially correct |
124 ms |
4296 KB |
Partially correct |
| 11 |
Partially correct |
114 ms |
4284 KB |
Partially correct |
| 12 |
Partially correct |
116 ms |
4296 KB |
Partially correct |
| 13 |
Correct |
86 ms |
4296 KB |
Output is correct |
| 14 |
Correct |
42 ms |
4296 KB |
Output is correct |
| 15 |
Correct |
82 ms |
4288 KB |
Output is correct |
| 16 |
Correct |
90 ms |
4296 KB |
Output is correct |
| 17 |
Correct |
90 ms |
4296 KB |
Output is correct |
| 18 |
Correct |
72 ms |
4304 KB |
Output is correct |
