Submission #1295750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295750		mdobric	Zagonetka (COI18_zagonetka)	C++20	100 / 100	31 ms	496 KiB

zagonetka

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 105;
int n, p[maxn], p2[maxn], uvjet[maxn][maxn], pos[maxn], ans[maxn];
vector <int> v[maxn], v2[maxn];

int query (){
	cout << "query ";
	for (int i = 0; i < n; i++) cout << p2[i] << " ";
	cout << "\n";
	cout.flush();
	int ans;
	cin >> ans;
	return (ans + 1) % 2;
}

int calc (int a, int b){
	vector <int> veci, srednji, manji;
	if (uvjet[a][b] != -1) return uvjet[a][b];
	for (int i = p[a] + 1; i < p[b]; i++){
		if (calc(a, pos[i]) == 1) veci.push_back(pos[i]);
		else if (calc(pos[i], b) == 1) manji.push_back(pos[i]);
		else srednji.push_back(pos[i]);
		
		if (calc(a, pos[i]) == 1 and calc(pos[i], b) == 1) return uvjet[a][b] = 1;
	}
	int br = p[a];
	for (int i = 0; i < manji.size(); i++) p2[manji[i]] = br, br++;
	p2[b] = br, br++;
	for (int i = 0; i < srednji.size(); i++) p2[srednji[i]] = br, br++;
	p2[a] = br, br++;
	for (int i = 0; i < veci.size(); i++) p2[veci[i]] = br, br++;
	uvjet[a][b] = query();
	//cout << a << " " << b << "   " << uvjet[a][b] << endl;
	for (int i = 0; i < n; i++) p2[i] = p[i];
	return uvjet[a][b];
}

int solve (int x, int l){
	int ukp = 0;
	for (int i = 0; i < v[x].size(); i++){
		if (ans[v[x][i]] == 0) ukp++;
	}
	ans[x] = l + ukp;
	for (int i = 0; i < v[x].size(); i++){
		if (ans[v[x][i]] == 0) l += solve(v[x][i], l);
	}
	return ukp + 1;
}

int solve2 (int x, int l){
	int ukp = 0;
	for (int i = 0; i < v2[x].size(); i++){
		if (ans[v2[x][i]] == 0) ukp++;
	}
	ans[x] = l - ukp;
	for (int i = 0; i < v2[x].size(); i++){
		if (ans[v2[x][i]] == 0) l -= solve2(v2[x][i], l);
	}
	return ukp + 1;
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i], pos[p[i]] = i, p2[i] = p[i];
	memset(uvjet, -1, sizeof uvjet);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i] >= p[j]) uvjet[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (calc(i, j) == 1) v[j].push_back(i), v2[i].push_back(j);
		}
	}
	for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end()); 
	cout << "end" << "\n";
	cout.flush();
	int br = 1;
	for (int i = 0; i < n; i++){
		if (ans[i] == 0) br += solve(i, br);
	}
	for (int i = 0; i < n; i++) cout << ans[i] << " ";
	cout << "\n";
	cout.flush();
	memset(ans, 0, sizeof ans);
	br = n;
	for (int i = 0; i < n; i++){
		if (ans[i] == 0) br -= solve2(i, br);
	}
	for (int i = 0; i < n; i++) cout << ans[i] << " ";
	cout << "\n";
	cout.flush();
	
	return 0;
}

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