oj.uz

Submission #647340

# Submission time Handle Problem Language Result Execution time Memory
647340 2022-10-02T08:56:19 Z myrcella Zagonetka (COI18_zagonetka) C++17
9 / 100
 211 ms 432 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;
	auto time1=clock();
	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]--;
		}
	}
	auto time2=clock();
	assert(time2-time1<=2000);
	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 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 288 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 420 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
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 Runtime error 7 ms 432 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 211 ms 428 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -