#include "key.h"
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>G[1010];
vector<int>U[1010], B[1010], V[1010];
int S[1010][1010], Nxt[1010], vis[1010];
int Num[1010], D[1010];
vector<int>T[1010];
void Go(int i, int x) {
if (U[i].empty()) {
U[i].push_back(x);
return;
}
int b = 1, e = U[i].size(), mid, r = 0, j;
while (b <= e) {
mid = (b + e) >> 1;
for (j = 0; j < mid; j++) {
TakeKey(U[i][j]);
}
TakeKey(x);
if (Explore() == i * (mid + 1)) {
r = mid;
b = mid + 1;
}
else e = mid - 1;
}
if (r == U[i].size()) {
U[i].push_back(x);
}
else {
Num[x] = U[i][r];
}
}
void TakeAll(int b, int e) {
int i;
for (i = b; i <= e; i++) {
for (auto &x : V[i])TakeKey(x);
}
}
void EnsureKeyInfo(int N) {
int i, j, k;
for (i = 1; i <= N; i++) {
TakeKey(i);
int t = Explore();
G[t].push_back(i);
}
int Mn = -1;
for (i = 1; i <= N; i++) {
if (G[i].empty())continue;
if (Mn == -1) {
Mn = i;
for (auto &x : G[i]) {
Go(i, x);
}
}
else {
for (auto &x : G[i]) {
TakeAll(1, i - 1);
TakeKey(x);
if (Explore() == D[i - 1] + i) {
Go(i, x);
continue;
}
int b = 1, e = V[i - 1].size() - 1, r = V[i - 1].size(), mid;
while (b <= e) {
mid = (b + e) >> 1;
TakeAll(1, i - 2);
for (j = 0; j < mid; j++) {
TakeKey(V[i - 1][j]);
}
TakeKey(x);
int t = Explore();
if (S[i - 1][mid] + 1 == t) {
r = mid;
e = mid - 1;
}
else b = mid + 1;
}
Nxt[x] = V[i - 1][r - 1];
B[i].push_back(x);
}
}
for (auto &x : U[i])V[i].push_back(x);
for (auto &x : B[i])V[i].push_back(x);
for (j = 0; j <= V[i].size(); j++) {
if (j == 0) {
if (Mn == i)S[i][j] = 0;
else S[i][j] = D[i - 1];
continue;
}
TakeAll(1, i - 1);
for (k = 0; k < j; k++)TakeKey(V[i][k]);
S[i][j] = Explore();
}
D[i] = S[i][V[i].size()];
}
for (i = 1; i <= N; i++)for (auto &x : U[i])Num[x] = x;
for (i = 1; i <= N; i++) {
if (Num[i]) {
for (j = 1; j <= N; j++) {
if (Num[j] == Num[i])Report(i, j);
}
continue;
}
else {
for (j = 1; j <= N; j++)vis[j] = 0;
int x = i;
while (x) {
vis[x] = 1;
x = Nxt[x];
}
for (j = 1; j <= N; j++) {
if (vis[j] || vis[Num[j]])Report(i, j);
}
}
}
}
Compilation message
key.cpp: In function 'void Go(int, int)':
key.cpp:32:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r == U[i].size()) {
~~^~~~~~~~~~~~~~
key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j <= V[i].size(); j++) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
1384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
1384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
1384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
