Submission #647301

#	Time	Username	Problem	Language	Result	Execution time	Memory
647301		myrcella	Zagonetka (COI18_zagonetka)	C++17	18 / 100	3040 ms	312 KiB

zagonetka

//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();
		}
	}
	cout<<"end"<<endl;
	rep(i,0,n) cout<<amin[i]<<" ";
	cout<<endl;
	rep(i,0,n) cout<<amax[i]<<" ";
	cout<<endl;
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 18 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51