#include<bits/stdc++.h>
#include"grader.h"
using namespace std;
const int maxn = 260;
int MAGIC = 12;
mt19937 rng(69420);
int n = 260;
vector<int> crr;
int cnt[maxn][maxn];
int pp[maxn][maxn];
int dead[maxn][maxn];
vector<int> possible[maxn];
vector<vector<int>> amon;
vector<int> perm;
void backtrack(int pos) {
if(pos == n+1){
amon.push_back(crr);
return;
}
for(int i: possible[pos]){
if(crr[i]){
continue;
}
bool chk = 1;
for(int j = 0; j < MAGIC; j++){
int tmp = i - pp[j][pos];
tmp*=-1;
if(tmp < 0)tmp += n;
if(!cnt[j][tmp]){
chk = 0;
break;
}
}
if(!chk)continue;
for(int j = 0; j < MAGIC; j++){
int tmp = i - pp[j][pos];
tmp*=-1;
if(tmp < 0)tmp += n;
cnt[j][tmp]--;
}
crr[i] = pos;
backtrack(pos+1);
crr[i] = 0;
for(int j = 0; j < MAGIC; j++){
int tmp = i - pp[j][pos];
tmp*=-1;
if(tmp < 0)tmp += n;
cnt[j][tmp]++;
}
}
}
// int query(vector<int> Q){
// int cnt = 0;
// for(int i = 0; i < n; i++){
// if(Q[i] == perm[i])cnt++;
// }
// // cout << cnt << endl;
// return cnt;
// }
void solve(int N){
n = N;
if(n <= 50)MAGIC = 7;
else MAGIC = 12;
crr.assign(n, 0);
for(int i = 1; i <= n; i++)perm.push_back(i);
shuffle(perm.begin(), perm.end(), rng);
vector<int> rd = perm;
for(int i = 0; i < MAGIC; i++){
shuffle(rd.begin(), rd.end(), rng);
for(int j = 0; j < n; j++)pp[i][rd[j]] = j;
for(int j = 0; j < n; j++){
cnt[i][j] = query(rd);
if(cnt[i][j] == n)return;
if(cnt[i][j] == 0){
for(int k = 0; k < n; k++)dead[rd[j]][j] = 1;
}
rd.push_back(rd[0]);
rd.erase(rd.begin());
}
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < n; j++)if(!dead[i][j])possible[i].push_back(j);
// cout << possible[i].size() << endl;
}
// return;
backtrack(1);
// cout << amon.size();
query(amon[0]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
456 KB |
Correct! Number of queries: 50 |
2 |
Correct |
0 ms |
464 KB |
Correct! Number of queries: 29 |
3 |
Correct |
0 ms |
600 KB |
Correct! Number of queries: 43 |
4 |
Correct |
1 ms |
456 KB |
Correct! Number of queries: 50 |
5 |
Correct |
1 ms |
456 KB |
Correct! Number of queries: 50 |
6 |
Correct |
0 ms |
464 KB |
Correct! Number of queries: 50 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
456 KB |
Correct! Number of queries: 50 |
2 |
Correct |
0 ms |
464 KB |
Correct! Number of queries: 29 |
3 |
Correct |
0 ms |
600 KB |
Correct! Number of queries: 43 |
4 |
Correct |
1 ms |
456 KB |
Correct! Number of queries: 50 |
5 |
Correct |
1 ms |
456 KB |
Correct! Number of queries: 50 |
6 |
Correct |
0 ms |
464 KB |
Correct! Number of queries: 50 |
7 |
Correct |
3 ms |
712 KB |
Correct! Number of queries: 400 |
8 |
Correct |
5 ms |
708 KB |
Correct! Number of queries: 400 |
9 |
Correct |
3 ms |
712 KB |
Correct! Number of queries: 400 |
10 |
Correct |
4 ms |
768 KB |
Correct! Number of queries: 400 |
11 |
Correct |
2 ms |
716 KB |
Correct! Number of queries: 300 |
12 |
Correct |
3 ms |
972 KB |
Correct! Number of queries: 400 |
13 |
Correct |
4 ms |
968 KB |
Correct! Number of queries: 400 |
14 |
Correct |
3 ms |
712 KB |
Correct! Number of queries: 400 |
15 |
Correct |
3 ms |
720 KB |
Correct! Number of queries: 400 |
16 |
Correct |
9 ms |
1480 KB |
Correct! Number of queries: 400 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
456 KB |
Correct! Number of queries: 50 |
2 |
Correct |
0 ms |
464 KB |
Correct! Number of queries: 29 |
3 |
Correct |
0 ms |
600 KB |
Correct! Number of queries: 43 |
4 |
Correct |
1 ms |
456 KB |
Correct! Number of queries: 50 |
5 |
Correct |
1 ms |
456 KB |
Correct! Number of queries: 50 |
6 |
Correct |
0 ms |
464 KB |
Correct! Number of queries: 50 |
7 |
Correct |
3 ms |
712 KB |
Correct! Number of queries: 400 |
8 |
Correct |
5 ms |
708 KB |
Correct! Number of queries: 400 |
9 |
Correct |
3 ms |
712 KB |
Correct! Number of queries: 400 |
10 |
Correct |
4 ms |
768 KB |
Correct! Number of queries: 400 |
11 |
Correct |
2 ms |
716 KB |
Correct! Number of queries: 300 |
12 |
Correct |
3 ms |
972 KB |
Correct! Number of queries: 400 |
13 |
Correct |
4 ms |
968 KB |
Correct! Number of queries: 400 |
14 |
Correct |
3 ms |
712 KB |
Correct! Number of queries: 400 |
15 |
Correct |
3 ms |
720 KB |
Correct! Number of queries: 400 |
16 |
Correct |
9 ms |
1480 KB |
Correct! Number of queries: 400 |
17 |
Correct |
160 ms |
1484 KB |
Correct! Number of queries: 3100 |
18 |
Correct |
375 ms |
1616 KB |
Correct! Number of queries: 3000 |
19 |
Correct |
96 ms |
1744 KB |
Correct! Number of queries: 3000 |
20 |
Correct |
70 ms |
1788 KB |
Correct! Number of queries: 3100 |
21 |
Correct |
102 ms |
2052 KB |
Correct! Number of queries: 3000 |
22 |
Correct |
320 ms |
1592 KB |
Correct! Number of queries: 3000 |
23 |
Correct |
233 ms |
2168 KB |
Correct! Number of queries: 3000 |
24 |
Correct |
341 ms |
1548 KB |
Correct! Number of queries: 3100 |
25 |
Correct |
404 ms |
1220 KB |
Correct! Number of queries: 3100 |
26 |
Correct |
645 ms |
1496 KB |
Correct! Number of queries: 3100 |