oj.uz

Submission #70443

# Submission time Handle Problem Language Result Execution time Memory
70443 2018-08-22T22:35:14 Z Bruteforceman Zagonetka (COI18_zagonetka) C++11
27 / 100
 3000 ms 640 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];
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];

int dp(int x) {
	mx[x] = mn[x] = x;
	for(auto i : g[x]) {
		if(!vis[i]) dp(i);
		mx[x] = max(mx[x], mx[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;
	}
	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]);
					dfs(p[j]);
					// cerr << p[i] << ' ' << p[j] << endl;
				}
			}
		}
	}
	cout << "end" << endl;

	memset(vis, false, sizeof vis);
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			dp(i);
		}
	}

	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];
		}
	}
	for(int i = 0; i < n; i++) {
		if(in[i] == 0) {
			Q.push(pii(mn[i], i));
			P.push(pii(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 : g[i]) {
			++in[j];
		}
	}
	while(!P.empty()) {
		int x = P.top().second;
		P.pop();
		big.push_back(x);
		// cerr << "adding " << x << endl;
		for(int i : g[x]) {
			--in[i];
			if(in[i] == 0) {
				P.push(pii(i, i));
			}
		}
	}

	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;
}

Compilation message

zagonetka.cpp: In function 'int dp(int)':
zagonetka.cpp:43:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 640 KB Output is correct
2 Correct 37 ms 640 KB Output is correct
3 Correct 43 ms 640 KB Output is correct
4 Correct 53 ms 640 KB Output is correct
5 Correct 14 ms 640 KB Output is correct
6 Correct 49 ms 640 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 46 ms 640 KB Output is correct
10 Correct 25 ms 640 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 640 KB Output is correct
2 Correct 114 ms 640 KB Output is correct
3 Correct 84 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Execution timed out 3010 ms 640 KB Time limit exceeded
8 Halted 0 ms 0 KB -