Submission #647338

#TimeUsernameProblemLanguageResultExecution timeMemory
647338myrcellaZagonetka (COI18_zagonetka)C++17
0 / 100
197 ms464 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]; bool edge[maxn][maxn]; int val[maxn]; int n; int cnt[maxn]; int deg[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; } 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]++; 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]--; } } assert(1==22); 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; 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...