oj.uz

Submission #70636

# Submission time Handle Problem Language Result Execution time Memory
70636 2018-08-23T07:56:48 Z Bruteforceman Zagonetka (COI18_zagonetka) C++11
18 / 100
 3000 ms 656 KB 
#include "bits/stdc++.h"
using namespace std;
int n;
vector <int> p;
 
bool query(vector <int> v) {
	vector <int> p (v.size());
	for(size_t i = 0; i < v.size(); i++) {
		p[v[i]] = i;
	}
	cout << "query";
	for(auto i : p) {
		cout << " " << (i+1);
	}
	cout << endl;
	int ans;
	cin >> ans;
	return ans;
}
 
vector <int> g[111];
vector <int> rev[111];
bool vis[111];
void dfs(int x) {
	vis[x] = true;
	for(auto i : g[x]) {
		if(!vis[i]) {
			dfs(i);
		}
	}
} 
 
int mx[111];
int mn[111];
int in[111];
 
void dp(int x) {
	mn[x] = x;
	for(auto i : g[x]) {
		if(!vis[i]) dp(i);
		mn[x] = min(mn[x], mn[i]);
	}
}
void fn(int x) {
	mn[x] = x;
	for(auto i : rev[x]) {
		if(!vis[i]) fn(i);
		mn[x] = min(mn[x], mn[i]);
	}
}
 
int main(int argc, char const *argv[])
{
	cin >> n;
	p.resize(n);
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		p[x-1] = i;
	}
	int cnt = 0;
	for(int i = n-1; i >= 0; i--) {
		memset(vis, false, sizeof vis);
		for(int j = i+1; j < n; j++) {
			if(vis[p[j]] == false) {	
				// cout << p[i]+1 << " with " << p[j]+1 << endl;
				vector <int> tmp;
				for(int k = 0; k < i; k++) {
					tmp.emplace_back(p[k]);
				}
				for(int k = i+1; k <= j; k++) {
					if(vis[p[k]] == false) {
						tmp.emplace_back(p[k]);
					}
				}
				tmp.emplace_back(p[i]);
				for(int k = i+1; k < n; k++) {
					if(vis[p[k]] == false && k <= j) continue;
					tmp.emplace_back(p[k]);
				}
				if(query(tmp) == 0) {
					g[p[i]].emplace_back(p[j]);
					rev[p[j]].emplace_back(p[i]);
					dfs(p[j]);
					// cerr << p[i]+1 << ' ' << p[j]+1 << endl;
					++cnt;
				}
			}
		}
	}
	// cerr << cnt << endl;
	cout << "end" << endl;
 
	typedef pair <int, int> pii;
	priority_queue <pii> P;
	priority_queue <pii, vector <pii>, greater <pii>> Q;
	vector <int> small, big;
 
	memset(in, 0, sizeof in);
	for(int i = 0; i < n; i++) {
		for(int j : g[i]) {
			++in[j];
		}
	}
	memset(vis, false, sizeof vis);
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			dp(i);
		}
	}
	for(int i = 0; i < n; i++) {
		if(in[i] == 0) {
			Q.push(pii(mn[i], i));
		}
	}
	while(!Q.empty()) {
		int x = Q.top().second;
		Q.pop();
		small.push_back(x);
		for(int i : g[x]) {
			--in[i];
			if(in[i] == 0) {
				Q.push(pii(mn[i], i));
			}
		}
	}
 
	memset(in, 0, sizeof in);
	for(int i = 0; i < n; i++) {
		for(int j : rev[i]) {
			++in[j];
		}
	}
	memset(vis, false, sizeof vis);
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			fn(i);
		}
	}
	for(int i = 0; i < n; i++) {
		if(in[i] == 0) {
			Q.push(pii(mn[i], i));
		}
	}
	while(!Q.empty()) {
		int x = Q.top().second;
		Q.pop();
		big.push_back(x);
		for(int i : rev[x]) {
			--in[i];
			if(in[i] == 0) {
				Q.push(pii(mn[i], i));
			}
		}
	}
	reverse(big.begin(), big.end());
 
	vector <int> ans (n);
	for(int i = 0; i < n; i++) {
		ans[small[i]] = i;
	}
	for(int i : ans) {
		cout << i+1 << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++) {
		ans[big[i]] = i;
	}
	for(int i : ans) {
		cout << i+1 << ' ';
	}
	cout << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 508 KB Output is correct
6 Incorrect 3 ms 508 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 508 KB Output is correct
2 Correct 40 ms 520 KB Output is correct
3 Correct 34 ms 524 KB Output is correct
4 Correct 53 ms 656 KB Output is correct
5 Correct 16 ms 656 KB Output is correct
6 Correct 47 ms 656 KB Output is correct
7 Correct 8 ms 656 KB Output is correct
8 Correct 8 ms 656 KB Output is correct
9 Correct 27 ms 656 KB Output is correct
10 Correct 21 ms 656 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 656 KB Output is correct
2 Incorrect 3 ms 656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 656 KB Output is correct
2 Correct 89 ms 656 KB Output is correct
3 Correct 96 ms 656 KB Output is correct
4 Correct 5 ms 656 KB Output is correct
5 Correct 5 ms 656 KB Output is correct
6 Correct 6 ms 656 KB Output is correct
7 Execution timed out 3098 ms 656 KB Time limit exceeded
8 Halted 0 ms 0 KB -