#include "key.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int NN, ba[1010], self[1010], par[1010], ccn, ld[1010], cns[1010];
// par[i] = -x (i is in cycle x), ld[x] = leader of cycle x, cns[x] = nodes of cycle x
vector<int> lds[1010]; // lds[i] : leaders that ba[x]=i
int chk[1010], sum;
void TakeKey2(int K){
while(chk[K]){
chk[K]=1, sum++;
K=par[K];
if(K<0){
K=ld[-K];
if(!chk[K]) chk[K]=1, sum+=cns[K];
break;
}
}
}
int ExploreKey(vector<int> &v, int s, int e, int pl){
if(pl){
TakeKey(pl);
for(int i=s; i<=e; i++){
if(v[i]<0) TakeKey(ld[-v[i]]);
else TakeKey(v[i]);
}
return Explore();
}
sum=0;
for(int i=1; i<=NN; i++) chk[i]=0;
for(int i=s; i<=e; i++){
if(v[i]<0) TakeKey2(ld[-v[i]]);
else TakeKey2(v[i]);
}
return sum;
}
int cmp(const int &x, const int &y){
return self[x] < self[y];
}
int para(int ix, vector<int> &v){
int mi=0, mx=v.size(), md;
v.push_back(0);
while(1){
md = (mi+mx)/2;
if(mi==mx) break;
if(ExploreKey(v, mi, md, ix) <= ExploreKey(v, mi, md, 0)+1) mx=md;
else mi=md+1;
}
md = v[md];
v.pop_back();
return md;
}
void EnsureKeyInfo(int N) {
NN = N;
for(int i=1; i<=N; i++){
TakeKey(i);
self[i]=Explore();
}
for(int i=0; i<N; i++) ba[i]=i+1;
sort(ba, ba+N, cmp);
for(int t=0; t<N; t++){
int i=ba[t];
par[i]=para(i, lds[self[i]-1]);
if(par[i]<=0){
if(par[i]==0){
par[i]=-(++ccn), ld[ccn]=i;
if(self[i]>1) lds[self[i]-1].push_back(-ccn);
lds[self[i]].push_back(i);
}
cns[-par[i]]++;
}
else lds[self[i]].push_back(i);
}
for(int i=1; i<=N; i++){
int t=i;
for(; par[t]>0; t=par[t]) Report(i, t);
for(int j=1; j<=N; j++){
if(par[t] == par[j]) Report(i, j);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
744 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
744 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
744 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
