Submission #45007

#	Time	Username	Problem	Language	Result	Execution time	Memory
45007		Xellos	Zagonetka (COI18_zagonetka)	C++14	100 / 100	92 ms	716 KiB

zagonetka

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define sgn(x) (((x) < 0)?-1:1)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

void solve(int N, vector< vector<int> > &G, vector<int> &D, vector<int> &P, vector<bool> bl, vector<bool> bl_inv) {
	for(int i = 0; i < N; i++) if(P[i] == -1 && !bl[i]) {
		queue<int> q;
		q.push(i);
		vector<bool> bl_nw = bl;
		bl_nw[i] = 1;
		int cnt = 0;
		while(!q.empty()) {
			ALL_THE(G[q.front()], it) if(!bl_nw[*it]) {
				bl_nw[*it] = 1;
				cnt++;
				q.push(*it);
			}
			q.pop();
		}
		vector<bool> bl_inv_nw = bl_inv;
		for(int j = 0; j < N; j++) if(!bl_inv[j]) {
			bl_inv_nw[j] = 1;
			if(cnt) {
				cnt--;
				continue;
			}
			bl[i] = 1;
			bl_inv[j] = 1;
			P[i] = j;
			break;
		}
		for(int j = 0; j < N; j++) if(!bl_nw[j]) bl[j] = 1;
		for(int j = 0; j < N; j++) if(!bl_inv_nw[j]) bl_inv[j] = 1;
		solve(N, G, D, P, bl_nw, bl_inv_nw);
		solve(N, G, D, P, bl, bl_inv);
		break;
	}
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<int> P(N), Pi(N);
	for(int i = 0; i < N; i++) {
		cin >> P[i];
		Pi[--P[i]] = i;
	}

	vector< vector<bool> > cond(N, vector<bool>(N, 0));
	for(int l = 1; l <= N; l++) {
		for(int i = 0; i < N-l; i++) for(int k = 1; k < l; k++)
			if(cond[Pi[i]][Pi[i+k]] && cond[Pi[i+k]][Pi[i+l]]) cond[Pi[i]][Pi[i+l]] = 1;
		for(int i = 0; i < N-l; i++) if(!cond[Pi[i]][Pi[i+l]]) {
			int x = Pi[i], y = Pi[i+l];
			vector<int> Pi_q = Pi, Pq = P;

			vector<bool> vis_gx(N, 0), vis_ly(N, 0);
			queue<int> q;
			q.push(i);
			vis_gx[i] = true;
			while(!q.empty()) {
				for(int j = q.front(); j <= i+l; j++) if(cond[Pi[q.front()]][Pi[j]] && !vis_gx[j]) {
					vis_gx[j] = true;
					q.push(j);
				}
				q.pop();
			}
			q.push(i+l);
			vis_ly[i+l] = true;
			while(!q.empty()) {
				for(int j = q.front(); j >= i; j--) if(cond[Pi[q.front()]][Pi[j]] && !vis_ly[j]) {
					vis_ly[j] = true;
					q.push(j);
				}
				q.pop();
			}
			int a = i;
			for(int j = i; j <= i+l; j++) if(vis_ly[j]) {
				Pi_q[a] = Pi[j];
				a++;
			}
			for(int j = i; j <= i+l; j++) if(!vis_gx[j] && !vis_ly[j]) {
				Pi_q[a] = Pi[j];
				a++;
			}
			for(int j = i; j <= i+l; j++) if(vis_gx[j]) {
				Pi_q[a] = Pi[j];
				a++;
			}

			for(int j = 0; j < N; j++) Pq[Pi_q[j]] = j;
			cout << "query ";
			for(int j = 0; j < N; j++) cout << " " << Pq[j]+1;
			cout << endl;
			int ans;
			cin >> ans;
			if(ans == 0) cond[x][y] = cond[y][x] = 1;
		}
	}

	vector< vector<int> > G(N);
	vector<int> D(N, 0);
	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(cond[i][j] && P[i] < P[j]) {
		G[j].push_back(i);
		D[i]++;
	}
	vector<int> P_lexmin(N, -1);
	vector<bool> bl(N, 0), bl_inv(N, 0);
	solve(N, G, D, P_lexmin, bl, bl_inv);
	for(int i = 0; i < N; i++) {
		G[i].clear();
		D[i] = 0;
		bl[i] = bl_inv[i] = 0;
	}

	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(cond[i][j] && P[i] < P[j]) {
		G[i].push_back(j);
		D[j]++;
	}
	vector<int> P_lexmax(N, -1);
	solve(N, G, D, P_lexmax, bl, bl_inv);
	for(int i = 0; i < N; i++) P_lexmax[i] = N-1 - P_lexmax[i];

	cout << "end\n";
	for(int i = 0; i < N; i++) cout << P_lexmin[i]+1 << ((i == N-1)?"\n":" ");
	for(int i = 0; i < N; i++) cout << P_lexmax[i]+1 << ((i == N-1)?"\n":" ");
	return 0;}

// look at my code
// my code is amazing

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