Submission #969457

#	Time	Username	Problem	Language	Result	Execution time	Memory
969457		Tob	Zagonetka (COI18_zagonetka)	C++14	100 / 100	63 ms	1472 KiB

zagonetka

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef pair <ll, ll> pii;

const int N = 107;

int n, cur;
int p[N], pos[N], bio[N], ed[N][N], col[N], ins[N], resa[N], resb[N];
vector <pii> v, oe;
vector <int> adj[N], radj[N];

int Ask() {
	cout << "query ";
	for (int i = 0; i < n; i++) cout << col[i]+1 << " "; cout << endl;
	int o; cin >> o; return o;
//	for (auto it : oe) if (col[it.F] > col[it.S]) return 0;
//	return 1;
}

int dfs(int x) {
	bio[x] = 1;
	for (auto y : adj[x]) {
		if (bio[y] == 2) continue;
		if (bio[y] == 1) return 1;
		if (dfs(y)) return 1;
	}
	col[x] = cur--;
	bio[x] = 2;
	return 0;
}

int iter = 0;
void go(int x) {ins[x] = 1; for (auto y : adj[x]) if (!ins[y]) go(y);}
void rgo(int x) {ins[x] = 1; for (auto y : radj[x]) if (!ins[y]) rgo(y);}

void F(int l, int r, vector <int> sk) {
	if (l > r) return;
	if (l == r) {
		resa[sk[0]] = l;
		return;
	}
	memset(ins, 0, sizeof ins); go(sk[0]);
	vector <int> nea, neb;
	for (int i = 1; i < sk.size(); i++) {
		if (ins[sk[i]]) nea.pb(sk[i]);
		else neb.pb(sk[i]);
	}
	resa[sk[0]] = l+nea.size();
	F(l, resa[sk[0]]-1, nea);
	F(resa[sk[0]]+1, r, neb);
}
void G(int l, int r, vector <int> sk) {
	if (l > r) return;
	if (l == r) {
		resb[sk[0]] = l;
		return;
	}
	memset(ins, 0, sizeof ins); rgo(sk[0]);
	vector <int> nea, neb;
	for (int i = 1; i < sk.size(); i++) {
		if (ins[sk[i]]) nea.pb(sk[i]);
		else neb.pb(sk[i]);
	}
	resb[sk[0]] = r-nea.size();
	G(l, resb[sk[0]]-1, neb);
	G(resb[sk[0]]+1, r, nea);
}

int main () {
//	FIO;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> p[i]; p[i]--;
		pos[p[i]] = i;
	}
//	int q; cin >> q;
//	for (int i = 0; i < q; i++) {
//		int x, y; cin >> x >> y; x--; y--;
//		oe.pb({x, y});
//	}
	
	for (int j = 1; j < n; j++) {
		for (int i = 0; i+j < n; i++) {
			adj[pos[i+j]].pb(pos[i]);
			for (int k = 0; k < n; k++) col[k] = p[k];
			for (int k = i; k <= i+j; k++) {
				for (int l = i; l <= i+j; l++) {
					if (l == k) continue;
					if (ed[pos[k]][pos[l]]) adj[pos[k]].pb(pos[l]);
				}
			}
			cur = i+j;
			int ok = 0;
			for (int k = i; k <= i+j; k++) if (!bio[pos[k]]) {
				if (dfs(pos[k])) {
					ok = 1;
					break;
				}
			}
			if (ok) {
				ed[pos[i]][pos[i+j]] = 1;
				v.pb({pos[i], pos[i+j]});
			}
			else {
				if (!Ask()) {
					ed[pos[i]][pos[i+j]] = 1;
					v.pb({pos[i], pos[i+j]});
				}
			}
			memset(bio, 0, sizeof bio);
			memset(col, 0, sizeof col);
			for (int k = 0; k < n; k++) adj[k].clear();
		}
	}
	for (auto it : v) {
		radj[it.F].pb(it.S);
		adj[it.S].pb(it.F);
	}
	
	vector <int> tmp(n);
	for (int i = 0; i < n; i++) tmp[i] = i;
	F(0, n-1, tmp);
	G(0, n-1, tmp);
	cout << "end" << endl;
	for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
	for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;

	return 0;
}

Compilation message (stderr)

zagonetka.cpp: In function 'int Ask()':
zagonetka.cpp:23:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |  for (int i = 0; i < n; i++) cout << col[i]+1 << " "; cout << endl;
      |  ^~~
zagonetka.cpp:23:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |  for (int i = 0; i < n; i++) cout << col[i]+1 << " "; cout << endl;
      |                                                       ^~~~
zagonetka.cpp: In function 'void first(int, int, std::vector<int>)':
zagonetka.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 1; i < sk.size(); i++) {
      |                  ~~^~~~~~~~~~~
zagonetka.cpp: In function 'void G(int, int, std::vector<int>)':
zagonetka.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i = 1; i < sk.size(); i++) {
      |                  ~~^~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:135:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  135 |  for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
      |  ^~~
zagonetka.cpp:135:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  135 |  for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
      |                                                        ^~~~
zagonetka.cpp:136:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  136 |  for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
      |  ^~~
zagonetka.cpp:136:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  136 |  for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
      |                                                        ^~~~

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