oj.uz

답안 #233038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233038 2020-05-19T01:28:29 Z amoo_safar Zagonetka (COI18_zagonetka) C++14
0 / 100
 3000 ms 384 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 1e2 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll p[N], q[N], ind[N];
vector<ll> G[N], top;
ll L, R;
int mk[N], n;
void DFS(int u){
	mk[u] = 1;
	for(auto adj : G[u]) if(!mk[adj] && L <= p[adj] && p[adj] <= R) DFS(adj);
	top.pb(u);
}
bool Val(int x){
	memset(mk, 0, sizeof mk);
	top.clear();
	for(int i = L; i <= R; i++){
		if(!mk[ind[i]]){
			DFS(ind[i]);
		}
	}
	reverse(all(top));
	memcpy(q, p, sizeof p);
	//cerr << "$$ " << top.size() << '\n';
	//assert(top.size() == x);
	for(int i = L; i <= R; i++)
		q[top[i-L]] = i;
	cout << "query";
	for(int i = 1; i <= n; i++) cout << " " << q[i];
	cout << endl;
	int res;
	//res = (q[1] > q[2]) && (q[3] < q[4]);
	cin >> res;
	//debug(res);
	return res;
}

int g[N][N];

int mx[N], mn[N];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> p[i];
		ind[p[i]] = i;
	}
	for(int i = 2; i <= n; i++){
		for(int j = i - 1; j > 0; j--){
			L = j;
			R = i;
			G[ind[i]].pb(ind[j]);
			int rs = Val(i);
			G[ind[i]].pop_back();
			if(!rs){
				//cerr << "!! " << ind[j] << " " << ind[i] << '\n';
				G[ind[j]].pb(ind[i]);			
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(auto x : G[i]){
			cerr << i << ' ' << x << '\n';
			g[i][x] = 1;
		}
	}
	vector<int> vv(n);
	vector<int> Mn, Mx;
	iota(all(vv), 1);
	do {
		int fl = 1;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if((vv[i] > vv[j]) && (g[i+1][j+1])) fl = 0;
			}
		}
		if(fl) Mx = vv;
	} while(next_permutation(all(vv)));

	top.clear();
	memset(mk,0,sizeof mk);
	cout << "end" << endl;

	//for(auto al : Mn) cout << al << " ";
	//cout << '\n';

	for(int i = 1; i <= n; i++)
		for(int j = 0; j < n; j++)
			for(int k = 0; k < n; k ++)
				if(g[i][j] && g[j][k])
					g[i][k] = 1;
	iota(mn, mn + N, 0);
	vector<ll> v;
	for(int i = 1; i <= n; i++){
		int idx = -1;
		for(int k = 1; k <= n; k++) if(mn[k] == i) idx = i;
		int L = idx, R = idx;
		while((L > 0) && (mn[L] >= i)) L--;
		while((R <= n) && (mn[R] >= i)) R++;
		v.clear();
		for(int j = L + 1; j < R; j++)
			if(g[mn[j]][i]) v.pb(mn[j]);
		v.pb(i);
		for(int j = L + 1; j < R; j++)
			if(!g[mn[j]][i] && j != idx) v.pb(mn[j]);
		for(int j = L + 1; j < R; j++)
			mn[j] = v[j - L - 1];	
	}
	for(int i = 1; i <= n; i++)
		for(int k = 1; k <= n; k++) if(mn[k] == i) cout << k << " ";
	cout << endl;
	
	for(auto al : Mx) cout << al << " ";
	cout << endl;
	return 0;
}
/*
4
3 2 1 4


*/

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3037 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3079 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3014 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -