QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#697631 | #8819. CNOI Knowledge | real_sigma_team# | AC ✓ | 99ms | 4016kb | C++23 | 3.3kb | 2024-11-01 15:10:54 | 2024-11-01 15:10:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// строка -- это последовательность чисел от 1 до размера алфавита
std::vector<int> suffix_array (std::vector<int> s) {
if (s.size() == 1) return {0};
s.push_back(0); // добавляем нулевой символ в конец строки
int n = (int) s.size(),
cnt = 0, // вспомогательная переменная: счётчик для сортировки
cls = 0; // количество классов эквивалентности
std::vector<int> c(n), p(n);
std::map< int, std::vector<int> > t;
for (int i = 0; i < n; i++)
t[s[i]].push_back(i);
// «нулевой» этап
for (auto &x : t) {
for (int u : x.second)
c[u] = cls, p[cnt++] = u;
cls++;
}
// пока все суффиксы не стали уникальными
for (int l = 1; cls < n; l++) {
std::vector<std::vector<int> > a(cls); // массив для сортировки подсчётом
std::vector<int> _c(n); // новые классы эквивалентности
int d = (1<<l)/2;
int _cls = cnt = 0; // новое количество классов
for (int i = 0; i < n; i++) {
int k = (p[i]-d+n)%n;
a[c[k]].push_back(k);
}
for (int i = 0; i < cls; i++) {
for (size_t j = 0; j < a[i].size(); j++) {
// если суффикс начинает новый класс эквивалентности
if (j == 0 || c[(a[i][j]+d)%n] != c[(a[i][j-1]+d)%n])
_cls++;
_c[a[i][j]] = _cls-1;
p[cnt++] = a[i][j];
}
}
c = _c;
cls = _cls;
}
return std::vector<int>(p.begin()+1, p.end());
}
std::vector<int> calc_lcp(std::vector<int> &val, std::vector<int> &c, std::vector<int> &p) {
int n = val.size();
int current_lcp = 0;
std::vector<int> lcp(n);
for (int i = 0; i < n; i++) {
if (c[i] == n - 1)
continue;
int nxt = p[c[i] + 1];
while (max(i, nxt) + current_lcp < n && val[i + current_lcp] == val[nxt + current_lcp])
current_lcp++;
lcp[c[i]] = current_lcp;
current_lcp = max(0, current_lcp - 1);
}
return lcp;
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> a(n + 1);
auto calc = [&](int l, int r) -> int {
std::vector q(a.begin() + l, a.begin() + r + 1);
auto p = suffix_array(q);
std::vector<int> c(p.size());
for (int i = 0; i < p.size(); ++i) c[p[i]] = i;
auto lcp = calc_lcp(q, c, p);
int ans = q.size() * (q.size() + 1) / 2;
for (auto i : lcp) ans -= i;
return ans;
};
for (int i = 1; i <= n; ++i) {
a[i] = i;
int L = 0, R = i - 1;
while (L != R) {
int M = (L + R) / 2 + 1;
std::cout << "? " << M << ' ' << i << std::endl;
int res;
std::cin >> res;
if (calc(M, i) != res) L = M;
else R = M - 1;
}
if (L != 0) a[i] = a[L];
}
std::cout << "!";
for (int i = 1; i <= n; ++i) std::cout << ' ' << a[i];
std::cout << std::endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
12 3 3 6 6 10 6 10 15 10 15 21 10 20 15 14 6 9 14 27 34 43 19 5 2 19 5 8 25 9 13 19
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 2 6 ? 1 6 ? 4 7 ? 2 7 ? 3 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 3 9 ? 2 9 ? 1 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 8 11 ? 6 12 ? 9 12 ? 8 12 ? 7 12 ! 1 2 3 4 5 6 2 5 9 9 5 6
result:
ok Accepted. 31 queries used.
Test #2:
score: 0
Accepted
time: 92ms
memory: 3728kb
input:
1000 3 2 3 2 5 7 11 8 2 7 2 11 5 7 11 5 3 15 5 2 15 3 2 19 4 2 17 4 2 20 4 2 15 4 2 23 9 13 15 23 11 5 3 31 11 5 3 36 11 5 2 45 15 3 2 48 15 5 7 11 58 16 5 2 59 16 5 8 69 21 8 2 69 20 8 3 5 79 20 8 2 76 20 8 3 5 87 26 8 3 5 88 26 8 2 100 24 8 3 5 98 24 8 2 111 31 11 3 2 108 33 11 5 7 120 33 11 5 2 1...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 10 16 ? 9 16 ? 9 17 ? 13 17 ? 15 17 ? 16 17 ? 9...
result:
ok Accepted. 8229 queries used.
Test #3:
score: 0
Accepted
time: 82ms
memory: 3784kb
input:
1000 2 2 5 7 5 2 7 2 7 16 11 11 5 2 11 3 2 14 3 2 11 3 2 13 4 2 7 4 2 15 41 23 20 8 2 28 12 5 8 31 12 5 2 38 11 3 2 38 9 3 2 44 14 5 7 9 44 14 5 2 54 15 3 2 56 14 3 2 65 17 4 2 66 17 7 9 11 76 17 8 2 76 20 8 3 5 87 26 8 2 88 26 8 3 5 102 26 8 3 5 102 26 8 2 115 31 11 5 8 113 28 11 5 3 125 23 11 5 2 ...
output:
? 1 2 ? 2 3 ? 2 4 ? 1 4 ? 3 5 ? 4 5 ? 3 6 ? 5 6 ? 4 7 ? 2 7 ? 3 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 4 14 ? 6 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ? 15 17 ? 16 17 ? 9 ...
result:
ok Accepted. 8243 queries used.
Test #4:
score: 0
Accepted
time: 86ms
memory: 4012kb
input:
1000 3 3 5 5 2 5 8 8 2 8 3 5 12 5 2 11 3 2 16 5 7 11 15 5 3 20 7 3 5 21 8 2 27 7 2 26 4 2 31 5 3 2 27 5 3 2 31 5 3 2 26 5 3 2 35 11 15 17 26 35 14 5 3 44 15 5 2 44 15 3 2 53 19 4 2 55 19 7 9 14 63 19 8 3 5 62 19 8 2 69 24 7 2 70 23 7 15 11 81 23 8 3 5 83 25 7 3 5 99 33 11 5 2 105 34 11 5 8 120 33 11...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 7 10 ? 6 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 10 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 15 16 ? 9 17 ? 13 ...
result:
ok Accepted. 8262 queries used.
Test #5:
score: 0
Accepted
time: 85ms
memory: 3808kb
input:
1000 2 2 5 7 5 3 8 2 7 2 9 3 2 5 3 2 6 3 2 11 27 13 20 17 8 2 20 8 3 5 26 8 3 5 26 8 2 31 11 5 8 28 11 5 3 36 11 5 3 34 9 5 3 41 11 5 3 45 14 5 2 55 15 5 8 56 16 5 2 65 21 8 3 5 65 20 8 2 75 20 8 3 5 76 21 8 3 5 87 26 8 2 85 24 8 3 5 95 24 8 2 92 26 8 3 5 101 32 12 5 2 95 31 12 5 8 103 31 11 5 3 103...
output:
? 1 2 ? 2 3 ? 2 4 ? 1 4 ? 3 5 ? 4 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 3 11 ? 5 11 ? 4 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 11 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ? ...
result:
ok Accepted. 8231 queries used.
Test #6:
score: 0
Accepted
time: 91ms
memory: 3704kb
input:
1000 2 3 5 5 2 5 8 8 2 8 3 5 12 5 2 12 5 8 16 5 2 16 5 8 21 8 3 5 21 7 3 5 26 7 3 5 23 7 3 5 27 9 5 3 27 11 5 2 34 11 5 8 34 11 5 3 41 15 5 3 41 14 5 3 48 11 5 3 52 14 5 2 63 19 7 2 66 20 7 11 77 21 8 2 79 21 7 2 91 27 7 16 11 91 27 8 2 104 26 8 3 5 103 26 8 2 115 31 11 3 2 115 32 9 3 2 129 31 5 3 2...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 6 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 8 11 ? 6 12 ? 9 12 ? 11 12 ? 10 12 ? 7 13 ? 10 13 ? 12 13 ? 11 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 13 15 ? 8 16 ? 12 16 ? 14 16 ? 15...
result:
ok Accepted. 8227 queries used.
Test #7:
score: 0
Accepted
time: 85ms
memory: 3776kb
input:
1000 3 2 3 2 5 7 12 8 2 7 2 11 5 7 11 5 3 15 5 2 15 3 2 22 41 50 61 23 8 3 5 29 7 3 5 29 8 2 37 13 23 29 37 13 5 3 45 11 5 3 44 9 5 3 51 11 5 3 47 11 5 3 57 15 29 38 58 17 6 9 69 22 9 3 6 68 21 9 3 6 80 21 9 3 5 80 23 9 13 94 30 9 3 6 94 31 9 2 108 30 9 17 13 110 28 9 17 13 126 36 13 5 2 128 36 13 5...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 6 8 ? 5 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 3 12 ? 2 12 ? 1 12 ? 7 13 ? 10 13 ? 12 13 ? 11 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 10 16 ? 9 16 ? 9 17 ? 13 ...
result:
ok Accepted. 8343 queries used.
Test #8:
score: 0
Accepted
time: 99ms
memory: 3776kb
input:
1000 3 2 5 9 6 9 13 9 3 5 7 3 5 11 5 2 11 3 2 17 29 22 17 5 2 22 7 2 19 4 2 27 53 35 28 9 15 21 35 13 6 9 33 13 5 2 42 13 5 8 43 11 5 3 52 15 5 3 54 16 5 2 65 17 37 23 29 65 18 5 3 76 23 7 3 5 77 23 9 12 17 89 23 9 3 6 87 23 9 2 100 29 7 2 100 30 7 17 11 115 30 9 17 23 116 30 9 2 131 37 13 5 8 130 3...
output:
? 1 2 ? 2 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 1 5 ? 3 6 ? 5 6 ? 4 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 3 10 ? 4 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 4 14 ? 6 14 ? 8 15 ? 12 15 ? 10 15 ? 9 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ?...
result:
ok Accepted. 8343 queries used.
Test #9:
score: 0
Accepted
time: 77ms
memory: 3816kb
input:
1000 3 3 6 5 2 5 8 8 2 9 18 24 13 5 2 13 24 18 18 5 3 17 5 3 23 9 12 17 23 9 2 29 7 2 27 4 2 32 5 3 2 29 5 3 2 33 5 3 2 33 9 13 15 24 42 15 21 24 33 42 17 6 9 51 17 5 2 51 17 5 9 13 63 23 8 2 67 23 7 2 80 23 7 11 83 21 8 2 95 26 8 3 5 95 29 53 35 44 110 30 9 3 5 111 30 8 2 126 37 11 5 8 125 38 13 23...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 2 7 ? 1 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 3 9 ? 4 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 8 12 ? 7 12 ? 7 13 ? 10 13 ? 12 13 ? 7 14 ? 11 14 ? 13 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 15 16 ? 9 17 ? 13 17 ? 15 1...
result:
ok Accepted. 8323 queries used.
Test #10:
score: 0
Accepted
time: 99ms
memory: 4016kb
input:
1000 2 3 5 6 9 6 9 9 2 7 2 12 22 17 11 5 3 15 5 3 17 36 22 29 23 9 2 23 9 13 30 8 3 5 30 8 2 36 11 5 8 33 11 5 3 41 11 5 3 41 12 22 27 32 51 17 5 2 51 18 5 8 61 18 6 9 13 62 18 5 2 74 24 9 13 75 23 9 13 87 23 9 3 5 88 23 7 3 5 100 28 7 3 5 101 28 9 15 21 115 27 9 3 5 115 28 8 2 129 35 13 23 18 127 3...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 1 4 ? 3 5 ? 2 5 ? 3 6 ? 5 6 ? 4 7 ? 6 7 ? 4 8 ? 2 8 ? 3 8 ? 5 9 ? 7 9 ? 8 9 ? 5 10 ? 8 10 ? 9 10 ? 6 11 ? 3 11 ? 5 11 ? 4 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 9 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 13 16 ? 9 17 ? 13 17 ? 15 ...
result:
ok Accepted. 8319 queries used.
Test #11:
score: 0
Accepted
time: 98ms
memory: 3780kb
input:
1000 2 3 5 5 2 5 8 9 13 18 9 3 6 13 5 2 13 5 8 18 6 9 13 18 5 3 24 8 2 24 9 13 18 30 8 3 5 29 8 2 36 11 3 2 36 12 22 29 45 12 23 17 46 13 5 3 55 17 5 3 53 15 5 3 64 15 35 21 64 17 6 9 76 23 9 2 76 24 8 3 5 88 24 9 13 18 89 24 9 2 102 31 9 18 13 102 30 8 2 116 30 8 3 5 115 30 8 2 130 37 11 3 2 130 37...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 3 6 ? 2 6 ? 1 6 ? 4 7 ? 6 7 ? 5 7 ? 4 8 ? 6 8 ? 7 8 ? 5 9 ? 7 9 ? 6 9 ? 5 10 ? 8 10 ? 7 10 ? 6 10 ? 6 11 ? 9 11 ? 10 11 ? 6 12 ? 9 12 ? 11 12 ? 7 13 ? 10 13 ? 9 13 ? 8 13 ? 7 14 ? 11 14 ? 13 14 ? 12 14 ? 8 15 ? 12 15 ? 14 15 ? 8 16 ? 12 16 ? 14 16 ? 15 16 ...
result:
ok Accepted. 8322 queries used.
Extra Test:
score: 0
Extra Test Passed