Submission #647304

#TimeUsernameProblemLanguageResultExecution timeMemory
647304myrcellaZagonetka (COI18_zagonetka)C++17
18 / 100
3041 ms320 KiB
//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 int amin[maxn],amax[maxn]; int deg[maxn],deg1[maxn],deg2[maxn]; bool edge[maxn][maxn]; vector <int> edge1[maxn],edge2[maxn]; //edge1: u->v == u<v set <int> s; int n; void dfs1(int u) { for (int v:edge1[u]) { if (lst[v]==-1 or a[u]>a[lst[v]]) lst[v] = u; dfs1(v); } } void dfs2(int u) { for (int v:edge2[u]) { if (nxt[v]==-1 or a[u]<a[nxt[v]]) nxt[v] = u; dfs2(v); } } void solve() { memset(deg,0,sizeof(deg)); rep(i,1,n+1) rep(j,1,n+1) if (edge[i][j]==1) deg[j]++; 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]--; if (deg[v]==0) q.push(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; 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; edge[j][i]=1; 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; edge[j][i] = 0; } } /* 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(); } } solve(); 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) cout<<amin[i]<<" "; cout<<endl; rep(i,0,n) cout<<amax[i]<<" "; cout<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...