oj.uz

Submission #647819

# Submission time Handle Problem Language Result Execution time Memory
647819 2022-10-04T08:09:15 Z myrcella Zagonetka (COI18_zagonetka) C++17
100 / 100
 256 ms 292 KB 
//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]++;
			bool flag = false;
			rep(k,i+1,j) if (edge[i][k]&edge[k][j]) {flag=true;break;}
			
			if (flag==false) {
				solve();
				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]--;
		}
	}
	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;
}

Subtask #1
9.0 / 9.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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 208 KB Output is correct
2 Correct 53 ms 208 KB Output is correct
3 Correct 61 ms 208 KB Output is correct
4 Correct 90 ms 208 KB Output is correct
5 Correct 13 ms 208 KB Output is correct
6 Correct 69 ms 208 KB Output is correct
7 Correct 8 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct
9 Correct 70 ms 208 KB Output is correct
10 Correct 45 ms 208 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 9 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 4 ms 228 KB Output is correct
8 Correct 7 ms 208 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 2 ms 208 KB Output is correct
11 Correct 7 ms 208 KB Output is correct
12 Correct 8 ms 208 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 208 KB Output is correct
2 Correct 256 ms 208 KB Output is correct
3 Correct 179 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 41 ms 288 KB Output is correct
8 Correct 76 ms 208 KB Output is correct
9 Correct 62 ms 292 KB Output is correct
10 Correct 233 ms 208 KB Output is correct
11 Correct 185 ms 208 KB Output is correct
12 Correct 206 ms 208 KB Output is correct
13 Correct 231 ms 208 KB Output is correct
14 Correct 167 ms 292 KB Output is correct
15 Correct 244 ms 208 KB Output is correct
16 Correct 216 ms 208 KB Output is correct