QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489140 | #8819. CNOI Knowledge | Yansuan_HCl | WA | 112ms | 31308kb | C++14 | 2.3kb | 2024-07-24 18:33:26 | 2024-07-24 18:33:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define U(i,l,r) for (int i(l),END##i(r); i<=END##i; ++i)
#define D(i,l,r) for (int i(l),END##i(r); i>=END##i; --i)
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline))
#define vc vector
#define ar array
#define pb push_back
#define eb emplace_back
#define el '\n'
using ll = long long;
const int N = 1003;
int n; int dist[N][N]; int s[N];
// 子串对应从 everything 到终结点的路径
// struct sam {
// map<int, int> ch;
// int tag, link, len;
// } tr[N * 2]; int ptr, last;
// void init() { ptr = 0; tr[0].link = -1; last = 0; }
// void append(int c) {
// int p = ++ptr; tr[p].len = tr[last].len + 1;
// int u = last; last = p;
// while (u != -1 && !tr[u].ch[c]) {
// tr[u].ch[c] = p;
// u = tr[u].link;
// }
// if (u != -1) {
// int q = tr[u].ch[c];
// if (tr[q].len == tr[u].len + 1) tr[p].link = q;
// else {
// int r = ++ptr; tr[r] = tr[q]; tr[r].tag = 0; tr[r].len = tr[u].len + 1;
// tr[q].link = tr[p].link = r;
// while (u != -1 && tr[u].ch[c] == q) {
// tr[u].ch[c] = r;
// u = tr[u].link;
// }
// }
// }
const ll P = 998244353, BA = 114514;
ll pb[N];
ll hsh[N];
ll f[N][N];
unordered_map<ll, int> last;
void insert(int p, int c) {
hsh[p] = hsh[p - 1] * BA + c;
f[p][p] = 1;
int delta = 0, d[N] {};
D (i, p - 1, 1) {
ll h = ((hsh[p - 1] - hsh[i - 1] * pb[p - i]) % P + P) % P;
int j = last[h];
++d[j]; last[h] = i;
}
D (i, p - 1, 1) {
delta += d[i];
f[i][p] = f[i][p - 1] + (p - i + 1) - delta;
}
}
int ask(int l, int r) {
cout << "? " << l << ' ' << r << endl;
int v; cin >> v;
return v;
}
int main() {
pb[0] = 1; U (i, 1, N - 1) pb[i] = pb[i - 1] * BA % P;
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin >> n;
s[1] = 1;
insert(1, 1);
int p = 1;
U (i, 2, n) {
int l = 0, r = i - 1;
while (l < r) {
int mid((l + r + 1) >> 1), cur = ask(mid, i);
if (cur == ask(mid, i - 1) + (i - mid + 1))
// if (cur == f[mid][i - 1] + (i - mid + 1))
r = mid - 1;
else
l = mid;
}
if (l) s[i] = s[l];
else s[i] = ++p;
insert(i, s[i]);
}
cout << "!";
U (i, 1, n)
cout << ' ' << s[i];
cout << endl;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5700kb
input:
12 3 1 6 3 6 3 10 6 10 6 15 10 10 6 21 15 15 10 27 21 20 15 14 10 6 3 9 6 20 14 34 26 43 34 19 14 9 6 5 3 2 1 25 19 8 5 5 2 25 19 9 5 19 13
output:
? 1 2 ? 1 1 ? 1 3 ? 1 2 ? 2 4 ? 2 3 ? 1 4 ? 1 3 ? 2 5 ? 2 4 ? 1 5 ? 1 4 ? 3 6 ? 3 5 ? 1 6 ? 1 5 ? 3 7 ? 3 6 ? 1 7 ? 1 6 ? 2 7 ? 2 6 ? 4 8 ? 4 7 ? 6 8 ? 6 7 ? 5 8 ? 5 7 ? 4 9 ? 4 8 ? 2 9 ? 2 8 ? 1 9 ? 1 8 ? 5 10 ? 5 9 ? 7 10 ? 7 9 ? 8 10 ? 8 9 ? 9 10 ? 9 9 ? 5 11 ? 5 10 ? 8 11 ? 8 10 ? 9 11 ? 9 10 ? ...
result:
ok Accepted. 54 queries used.
Test #2:
score: -100
Wrong Answer
time: 112ms
memory: 31308kb
input:
1000 3 1 5 3 2 1 3 2 2 1 7 3 11 7 8 5 5 3 2 1 11 8 3 2 2 1 11 7 5 2 7 3 15 11 8 5 5 3 3 1 15 11 8 5 5 3 2 1 19 15 7 5 3 2 2 1 19 15 4 3 3 2 2 1 23 19 5 4 3 2 2 1 20 17 5 4 3 2 2 1 23 20 5 4 3 2 2 1 23 15 9 4 13 6 15 7 31 23 14 9 8 5 5 3 3 1 31 23 15 11 7 5 5 3 3 1 41 31 16 11 8 5 5 3 2 1 45 36 15 11...
output:
? 1 2 ? 1 1 ? 1 3 ? 1 2 ? 2 3 ? 2 2 ? 2 4 ? 2 3 ? 3 4 ? 3 3 ? 2 5 ? 2 4 ? 1 5 ? 1 4 ? 3 6 ? 3 5 ? 4 6 ? 4 5 ? 5 6 ? 5 5 ? 3 7 ? 3 6 ? 5 7 ? 5 6 ? 6 7 ? 6 6 ? 4 8 ? 4 7 ? 6 8 ? 6 7 ? 5 8 ? 5 7 ? 4 9 ? 4 8 ? 6 9 ? 6 8 ? 7 9 ? 7 8 ? 8 9 ? 8 8 ? 5 10 ? 5 9 ? 7 10 ? 7 9 ? 8 10 ? 8 9 ? 9 10 ? 9 9 ? 5 11 ?...
result:
wrong answer Too many queries.