QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489621 | #8819. CNOI Knowledge | _log_ | WA | 246ms | 28256kb | C++17 | 2.5kb | 2024-07-24 21:57:01 | 2024-07-24 21:57:01 |
Judging History
answer
# include <bits/stdc++.h>
# define maxn 1005
# define ull unsigned long long
# define rep(i, j, k) for(int i = j; i <= k; ++i)
using namespace std;
int n, a[maxn], tot;
int Hash1[maxn], d[maxn], pw[maxn];
int ans[maxn][maxn];
map<ull, int> mp;
namespace Garder {
int ans[10][10];
void init() {
ans[1][1] = 1; ans[1][2] = 3, ans[1][3] = 6; ans[1][4] = 9; ans[1][5] = 12; ans[1][6] = 18; ans[1][7] = 24; ans[1][8] = 31;
ans[2][2] = 1; ans[2][3] = 3; ans[2][4] = 5; ans[2][5] = 7; ans[2][6] = 12; ans[2][7] = 17; ans[2][8] = 24;
ans[3][3] = 1; ans[3][4] = 3; ans[3][5] = 5; ans[3][6] = 9; ans[3][7] = 13; ans[3][8] = 19;
ans[4][4] = 1; ans[4][5] = 3; ans[4][6] = 6; ans[4][7] = 9; ans[4][8] = 14;
ans[5][5] = 1; ans[5][6] = 3; ans[5][7] = 6; ans[5][8] = 10;
ans[6][6] = 1; ans[6][7] = 3; ans[6][8] = 6;
ans[7][7] = 1; ans[7][8] = 3;
ans[8][8] = 1;
}
}
int query(int l, int r) {
cout << "? " << l << ' ' << r << endl;
// cout << Garder::ans[l][r] << endl;
// ans[l][r] = Garder::ans[l][r];
cin >> ans[l][r];
return ans[l][r];
}
void update(int r) {
Hash1[r] = Hash1[r - 1] * 19260817 + a[r];
rep(i, 1, r) {
int hsh = Hash1[r] - Hash1[i - 1] * pw[r - i + 1], l = mp[hsh], len = r - i + 1;
// cerr << i << ' ' << r << ' ' << hsh << '\n';
if(!l) d[1]++, d[i + 1]--;
else d[l - len + 2]++, d[i + 1]--;
mp[hsh] = r;
}
rep(i, 1, r) d[i] = d[i - 1] + d[i];//, cerr << d[i] << ' '; cerr << '\n';
rep(i, 1, r) ans[i][r] = ans[i][r - 1] + d[i];//, cout << ans[i][r] << ' '; cout << '\n';
memset(d, 0, sizeof(d));
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); Garder::init();
// memset(ans, -1, sizeof(ans));
cin >> n; a[1] = ++tot; Hash1[1] = 1; ans[1][1] = 1; mp[1] = 1;
pw[0] = 1; rep(i, 1, n) pw[i] = pw[i - 1] * 19260817;
rep(i, 2, n) {
// rep(j, 1, i - 1) cout << ans[j][i - 1] << ' '; cout << '\n';
if(query(1, i) - ans[1][i - 1] == i) {a[i] = ++tot; update(i); continue;}
int l = 1, r = i, pos;
while(l <= r) {
int mid = l + r >> 1;
if(query(mid, i) - ans[mid][i - 1] == i - mid + 1) pos = mid - 1, r = mid - 1;
else l = mid + 1;
}
a[i] = a[pos];
update(i);
// cout << "pos " << pos << ' ' << tot << '\n';
// rep(j, 1, i) cout << a[i] << ' '; cout << '\n';
}
cout << "! ";
rep(i, 1, n) cout << a[i] << ' ';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
12 3 6 10 15 21 27 10 20 15 34 14 6 9 43 52 19 5 2 1 62 19 5 13 8 72 25 9 19
output:
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 4 7 ? 2 7 ? 3 7 ? 1 8 ? 4 8 ? 6 8 ? 5 8 ? 1 9 ? 1 10 ? 5 10 ? 8 10 ? 9 10 ? 10 10 ? 1 11 ? 6 11 ? 9 11 ? 7 11 ? 8 11 ? 1 12 ? 6 12 ? 9 12 ? 7 12 ! 1 2 3 4 5 6 2 5 7 7 5 6
result:
ok Accepted. 28 queries used.
Test #2:
score: -100
Wrong Answer
time: 246ms
memory: 28256kb
input:
1000 3 5 2 1 7 3 2 1 11 5 11 7 16 8 2 1 21 7 2 1 27 11 5 7 34 11 5 3 41 15 5 2 1 48 15 3 2 1 57 19 4 2 1 66 17 4 2 1 75 20 4 2 1 84 15 4 2 1 96 23 9 13 15 108 23 11 5 3 124 31 11 5 3 140 36 11 5 2 1 156 45 15 3 2 1 172 48 15 5 11 7 188 58 16 5 2 1 208 59 16 5 12 8 229 69 21 8 2 1 251 69 20 8 3 5 273...
output:
? 1 2 ? 1 3 ? 2 3 ? 3 3 ? 1 4 ? 2 4 ? 3 4 ? 4 4 ? 1 5 ? 3 5 ? 1 5 ? 2 5 ? 1 6 ? 3 6 ? 5 6 ? 6 6 ? 1 7 ? 4 7 ? 6 7 ? 7 7 ? 1 8 ? 4 8 ? 6 8 ? 5 8 ? 1 9 ? 5 9 ? 7 9 ? 8 9 ? 1 10 ? 5 10 ? 8 10 ? 9 10 ? 10 10 ? 1 11 ? 6 11 ? 9 11 ? 10 11 ? 11 11 ? 1 12 ? 6 12 ? 9 12 ? 11 12 ? 12 12 ? 1 13 ? 7 13 ? 10 13 ...
result:
wrong answer Wrong Answer.