#include "monster.h"
using namespace std;
vector<int> now, tmp;
int w[1002][1002];
int fight(int i, int j)
{
if(i == j) return 0;
if(w[i][j] == -1)
{
w[i][j] = Query(i, j);
w[j][i] = !w[i][j];
}
return w[i][j];
}
void dnc(int l, int r)
{
if(l == r) return;
int m = (l + r)/2;
dnc(l, m);
dnc(m+1, r);
for(int i=l,j=m+1,k=l;k<=r;k++)
{
if(i == m+1) tmp[k] = now[j++];
else if(j == r+1) tmp[k] = now[i++];
else if(fight(now[i], now[j]) == 0)
tmp[k] = now[i++];
else
tmp[k] = now[j++];
}
for(int i=l;i<=r;i++) now[i] = tmp[i];
}
vector<int> Solve(int N) {
vector<int> T(N);
now.resize(N);
tmp.resize(N);
for(int i=0;i<N;i++) now[i] = i;
for(int i=0;i<N;i++) for(int j=0;j<N;j++) w[i][j] = -1;
dnc(0, N-1);
for(int i=0;i<N;)
{
if(i == N-1) break;
else if(i == N-2) { swap(now[i], now[i+1]); break; }
else if(i == N-3)
{
if(fight(now[i-1], now[i])) swap(now[i+1], now[i+2]);
else swap(now[i], now[i+1]);
break;
}
else
{
int a = fight(now[i], now[i+2]);
int b = fight(now[i+1], now[i+3]);
if(a == 1 && b == 1)
{
swap(now[i+1], now[i+2]);
i += 4;
continue;
}
else if(a == 0 && b == 0)
{
swap(now[i], now[i+1]);
swap(now[i+2], now[i+3]);
i += 4;
continue;
}
else
{
int c = fight(now[i+2], now[i+4]);
if(c == 1)
{
swap(now[i], now[i+1]);
swap(now[i+3], now[i+4]);
i += 5;
continue;
}
else
{
swap(now[i+1], now[i+2]);
swap(now[i+3], now[i+4]);
i += 5;
continue;
}
}
}
}
for(int i=0;i<N;i++) T[now[i]] = i;
return T;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
200 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
200 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
102 ms |
4192 KB |
Wrong Answer [4] |
2 |
Halted |
0 ms |
0 KB |
- |