//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 111;
int a[maxn],pos[maxn],b[maxn];
int lst[maxn],nxt[maxn]; //lst[i] = j -> j<i
pii min1[maxn],min2[maxn];
int deg[maxn],deg1[maxn],deg2[maxn];
bool edge[maxn][maxn];
vector <int> edge1[maxn],edge2[maxn]; //edge1: u->v == u<v
int val[maxn];
int n;
int cnt[maxn];
int id[maxn];
void solve() {
queue <int> q;
rep(i,1,n+1) if(deg[i]==0) q.push(i);
memset(b,-1,sizeof(b));
int cur = 1;
while (!q.empty()) {
int u=q.front();
q.pop();
b[pos[u]]=cur++;
rep(v,1,n+1) {
if (edge[u][v]==0) continue;
deg[v]--;
cnt[v]++;
if (deg[v]==0) q.push(v);
}
}
rep(i,1,n+1) deg[i] += cnt[i],cnt[i]=0;
}
void dfs1(int u) {
min1[u] = {u,0};
for (int v:edge1[u]) {
dfs1(v);
min1[u] = min(min1[u],{min1[v].fi,min1[v].se+1});
}
}
void dfs2(int u) {
min2[u] = {u,0};
for (int v:edge2[u]) {
dfs2(v);
min2[u] = min(min2[u],{min2[v].fi,min2[v].se+1});
}
}
void solve1() {
pq <pair<pii,int>, vector<pair<pii,int>>, greater<pair<pii,int>> > q;
rep(i,0,n) if(deg1[i]==0) q.push({min1[i],i});
int cur = 1;
while (!q.empty()) {
int u=q.top().se;
// debug(u);
q.pop();
b[u]=cur++;
for (int v:edge1[u]){
deg1[v]--;
if (deg1[v]==0) q.push({min1[v],v});
}
}
}
void solve2() {
pq <pair<pii,int>, vector<pair<pii,int>>, greater<pair<pii,int>> > q;
rep(i,0,n) if (deg2[i]==0) q.push({min2[i],i});
int cur = n;
while (!q.empty()) {
int u = q.top().se;
q.pop();
b[u] = cur--;
for (int v:edge2[u]) {
deg2[v]--;
if (deg2[v]==0) q.push({min2[v],v});
}
}
}
int main() {
// freopen("input.txt","r",stdin);
cin>>n;
rep(i,0,n) cin>>a[i],pos[a[i]] = i;
rep(i,1,n+1)
rep(j,i+1,n+1) edge[i][j] = 1,deg[j]++;
memset(lst,-1,sizeof(lst));
memset(nxt,-1,sizeof(nxt));
rep(t,1,n){
for (int i=1;i+t<=n;i++) {
int j = i+t;
edge[i][j]=0,deg[j]--;
edge[j][i]=1,deg[i]++;
solve();
bool flag = false;
rep(i,0,n) {
if (b[i]==-1) flag=true;
}
int ans=0;
if (!flag) {
cout<<"query";
rep(k,0,n) cout<<" "<<b[k];
cout<<endl;
cin>>ans;
}
if (ans==0) edge[i][j] =1,deg[j]++;
edge[j][i] = 0,deg[i]--;
}
}
/*
rep(i,1,n+1) {
s.erase(i);
vector <int> tmp;
while (nxt[pos[i]]==-1) {
auto it = s.upper_bound(i);
if (it==s.end()) break;
int cur = *it;
debug(cur);
swap(a[pos[i]],a[pos[cur]]);
cout<<"query";
rep(k,0,n) cout<<" "<<a[k];
cout<<endl;
int ans;cin>>ans;
swap(a[pos[i]],a[pos[cur]]);
if (ans==0) {
nxt[pos[i]] = pos[cur];
edge[pos[i]].pb(pos[cur]);
deg[pos[cur]]++;
}
else tmp.pb(cur);
s.erase(cur);
}
while (!tmp.empty()) s.insert(tmp.back()),tmp.pop_back();
}
*/
rep(i,1,n+1)
rep(j,1,n+1) {
if (edge[i][j]==0) continue;
// debug(i),debug(j);
edge1[pos[i]].pb(pos[j]),deg1[pos[j]]++;
edge2[pos[j]].pb(pos[i]),deg2[pos[i]]++;
}
rep(i,0,n) {
if (deg1[i]==0) dfs1(i);
if (deg2[i]==0) dfs2(i);
}
/*
int curmin = 1,curmax = n;
rep(i,0,n) {
if (amin[i]==0) {
vector <int> tmp;
int pos = i;
while (pos!=-1 and amin[pos]==0) tmp.pb(pos),pos = lst[pos];
while (!tmp.empty()) amin[tmp.back()] = curmin++,tmp.pop_back();
}
if (amax[i]==0) {
vector <int> tmp;
int pos = i;
while (pos!=-1 and amax[pos]==0) tmp.pb(pos),pos = nxt[pos];
while (!tmp.empty()) amax[tmp.back()] = curmax--,tmp.pop_back();
}
}
solve2();
cout<<"query";
rep(i,0,n) cout<<" "<<b[i];
cout<<endl;
int err;cin>>err;
assert(err==1);
*/
cout<<"end"<<endl;
rep(i,0,n) val[i] = 1;
memset(id,0,sizeof(id));
int tot = 1;
rep(i,0,n) {
int cntt=0;
rep(j,i+1,n) if (id[j]==id[i] and edge[a[j]][a[i]]==1) cntt++;
cout<<val[i] + cntt<<" ";
rep(j,i+1,n) if (id[j]==id[i] and edge[a[j]][a[i]]==0) assert(val[j]==val[i]),val[j] = val[i]+cntt+1;
rep(j,i+1,n) if (id[j]==id[i] and edge[a[j]][a[i]]==1) id[j] = tot;
tot++;
}
cout<<endl;
memset(id,0,sizeof(id));
tot=1;
rep(i,0,n) val[i] = n;
rep(i,0,n) {
int cntt=0;
rep(j,i+1,n) if (id[j]==id[i] and edge[a[i]][a[j]]==1) cntt++;
cout<<val[i] - cntt<<" ";
rep(j,i+1,n) if (id[j]==id[i] and edge[a[i]][a[j]]==0) assert(val[j]==val[i]),val[j] = val[i]-cntt-1;
rep(j,i+1,n) if (id[j]==id[i] and edge[a[i]][a[j]]==1) id[j] = tot;
tot++;
}
cout<<endl;
/*
solve1();
rep(i,0,n) cout<<b[i]<<" ";
cout<<endl;
solve2();
rep(i,0,n) cout<<b[i]<<" ";
cout<<endl;
*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
208 KB |
Output is correct |
| 2 |
Correct |
46 ms |
208 KB |
Output is correct |
| 3 |
Correct |
61 ms |
208 KB |
Output is correct |
| 4 |
Correct |
74 ms |
208 KB |
Output is correct |
| 5 |
Correct |
13 ms |
208 KB |
Output is correct |
| 6 |
Correct |
76 ms |
208 KB |
Output is correct |
| 7 |
Correct |
8 ms |
208 KB |
Output is correct |
| 8 |
Correct |
7 ms |
208 KB |
Output is correct |
| 9 |
Correct |
58 ms |
208 KB |
Output is correct |
| 10 |
Correct |
26 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Correct |
2 ms |
208 KB |
Output is correct |
| 3 |
Correct |
5 ms |
356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
208 KB |
Output is correct |
| 5 |
Correct |
3 ms |
208 KB |
Output is correct |
| 6 |
Correct |
6 ms |
320 KB |
Output is correct |
| 7 |
Correct |
5 ms |
208 KB |
Output is correct |
| 8 |
Correct |
8 ms |
208 KB |
Output is correct |
| 9 |
Correct |
6 ms |
208 KB |
Output is correct |
| 10 |
Correct |
3 ms |
208 KB |
Output is correct |
| 11 |
Correct |
8 ms |
208 KB |
Output is correct |
| 12 |
Correct |
7 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
208 KB |
Output is correct |
| 2 |
Correct |
213 ms |
256 KB |
Output is correct |
| 3 |
Correct |
184 ms |
208 KB |
Output is correct |
| 4 |
Execution timed out |
3073 ms |
328 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
