oj.uz

Submission #45007

# Submission time Handle Problem Language Result Execution time Memory
45007 2018-04-10T14:20:59 Z Xellos Zagonetka (COI18_zagonetka) C++14
100 / 100
 92 ms 716 KB 
#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.0 / 9.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 628 KB Output is correct
2 Correct 28 ms 696 KB Output is correct
3 Correct 48 ms 696 KB Output is correct
4 Correct 49 ms 696 KB Output is correct
5 Correct 12 ms 696 KB Output is correct
6 Correct 39 ms 696 KB Output is correct
7 Correct 9 ms 696 KB Output is correct
8 Correct 8 ms 696 KB Output is correct
9 Correct 24 ms 700 KB Output is correct
10 Correct 15 ms 700 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 700 KB Output is correct
2 Correct 2 ms 700 KB Output is correct
3 Correct 7 ms 700 KB Output is correct
4 Correct 7 ms 700 KB Output is correct
5 Correct 5 ms 700 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 5 ms 700 KB Output is correct
8 Correct 7 ms 700 KB Output is correct
9 Correct 6 ms 700 KB Output is correct
10 Correct 4 ms 700 KB Output is correct
11 Correct 8 ms 700 KB Output is correct
12 Correct 7 ms 700 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 700 KB Output is correct
2 Correct 90 ms 700 KB Output is correct
3 Correct 80 ms 700 KB Output is correct
4 Correct 6 ms 700 KB Output is correct
5 Correct 5 ms 700 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 17 ms 700 KB Output is correct
8 Correct 25 ms 716 KB Output is correct
9 Correct 23 ms 716 KB Output is correct
10 Correct 88 ms 716 KB Output is correct
11 Correct 66 ms 716 KB Output is correct
12 Correct 65 ms 716 KB Output is correct
13 Correct 75 ms 716 KB Output is correct
14 Correct 70 ms 716 KB Output is correct
15 Correct 60 ms 716 KB Output is correct
16 Correct 72 ms 716 KB Output is correct