oj.uz

답안 #630067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630067 2022-08-15T15:38:45 Z Arnch 도서관 (JOI18_library) C++17
100 / 100
 222 ms 4320 KB 
#include<bits/stdc++.h>
#include "library.h"
using namespace std;

/*
	Query(vector<int> &m);
	Answer(vector<int> &res);
*/

#define Sz(x) (int)(x.size())
#define All(x) (x).begin(), (x).end()

const int N = 1e3 + 10;

bool mark[N], vis[N];
int e[N][N];

int Ask(vector<int> &ask) {
	for(int i = 1; i <= Sz(ask); i++) ask[i - 1] = mark[i];
	return Query(ask);
}

void Solve(int N) {
	int n = N;

	if(n == 1) {
		vector<int> ans = {1};
		Answer(ans);
		return;
	}

	vector<vector<int> > vc;
	
	vector<int> ask(N);

	for(int i = 1; i <= n; i++) {
		vc.push_back({i});
		while(true) {
			for(auto j : vc) 
				for(auto x : j) mark[x] = 1;

			int t = Ask(ask);
			if(t == Sz(vc)) break;

			for(auto j : vc)
				for(auto x : j) mark[x] = 0;


			vector<int> res = vc.back(); vc.pop_back();

			for(auto j : res) mark[j] = 1;
			int l = 0, r = Sz(vc);
			while(r - l > 1) {
				int mid = (l + r) >> 1;
				for(int i = l; i < mid; i++) {
					for(auto j : vc[i]) mark[j] = 1;
				}
				t = Ask(ask);

				for(int i = l; i < mid; i++) {
					for(auto j : vc[i]) mark[j] = 0;
				}

				if(t != mid - l + 1) r = mid;
				else l = mid;
			}
			for(auto j : res) mark[j] = 0;

			int u1 = res[0], u2 = res.back();
			int v1 = vc[l][0], v2 = vc[l].back();

			/*cout<<"^**********" <<endl;
			for(auto j : res) cout<<j <<' ';
			cout<<endl;
			for(auto j : vc[l]) cout<<j <<' ';
			cout<<"**********" <<endl;*/

			mark[u1] = mark[v1] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u1][v1] = e[v1][u1] = 1;
				mark[u1] = mark[v1] = 0;
		
				reverse(All(vc[l]));
				for(auto j : res) vc[l].push_back(j);
				res.clear();
		
				res = vc[l];
				vc.erase(vc.begin() + l);
				vc.push_back(res);
				
				continue;
			}
			mark[u1] = mark[v1] = 0;
			
			mark[u1] = mark[v2] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u1][v2] = e[v2][u1] = 1;
				mark[u1] = mark[v2] = 0;

				for(auto j : res) vc[l].push_back(j);
				res.clear();
				
				res = vc[l];
				vc.erase(vc.begin() + l);
				vc.push_back(res);

				continue;
			}
			mark[u1] = mark[v2] = 0;

			mark[u2] = mark[v1] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u2][v1] = e[v1][u2] = 1;
				mark[u2] = mark[v1] = 0;
		
				for(auto j : vc[l]) res.push_back(j);
				vc[l].swap(res);
				res.clear();
				
				res = vc[l];
				vc.erase(vc.begin() + l);
				vc.push_back(res);

				continue;
			}
			mark[u2] = mark[v1] = 0;
			
			mark[u2] = mark[v2] = 1;
			t = Ask(ask);
			if(t == 1) {
				e[u2][v2] = e[v2][u2] = 1;
				mark[u2] = mark[v2] = 0;
		
				reverse(All(res));
				for(auto j : res) vc[l].push_back(j);
				res.clear();
				
				res = vc[l];
				vc.erase(vc.begin() + l);
				vc.push_back(res);

				continue;
			}
			mark[u2] = mark[v2] = 0;	
		}
	}

	vector<int> res, ans;
	int u;
	for(int i = 1; i <= n; i++) {
		int cnt = 0;
		for(int j = 1; j <= n; j++) cnt += e[i][j];
		if(cnt == 1) {
			u = i;
			vis[u] = 1;
			break;
		}
	}
	res.push_back(u);
	while(!res.empty()) {
		int u = res.back();
		res.pop_back();
		ans.push_back(u);
		for(int j = 1; j <= n; j++) {
			if(e[u][j] && !vis[j]) {
				res.push_back(j);
				vis[j] = 1;
				break;
			}
		}
	}

	Answer(ans);

}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 952 KB # of queries: 1700
2 Correct 29 ms 1048 KB # of queries: 1680
3 Correct 25 ms 1016 KB # of queries: 1788
4 Correct 32 ms 1012 KB # of queries: 1745
5 Correct 31 ms 1052 KB # of queries: 1763
6 Correct 22 ms 1096 KB # of queries: 1770
7 Correct 20 ms 1076 KB # of queries: 1767
8 Correct 22 ms 1020 KB # of queries: 1682
9 Correct 15 ms 1084 KB # of queries: 1775
10 Correct 14 ms 732 KB # of queries: 1073
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 4
13 Correct 0 ms 208 KB # of queries: 7
14 Correct 1 ms 208 KB # of queries: 14
15 Correct 1 ms 336 KB # of queries: 81
16 Correct 3 ms 396 KB # of queries: 170

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 952 KB # of queries: 1700
2 Correct 29 ms 1048 KB # of queries: 1680
3 Correct 25 ms 1016 KB # of queries: 1788
4 Correct 32 ms 1012 KB # of queries: 1745
5 Correct 31 ms 1052 KB # of queries: 1763
6 Correct 22 ms 1096 KB # of queries: 1770
7 Correct 20 ms 1076 KB # of queries: 1767
8 Correct 22 ms 1020 KB # of queries: 1682
9 Correct 15 ms 1084 KB # of queries: 1775
10 Correct 14 ms 732 KB # of queries: 1073
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 4
13 Correct 0 ms 208 KB # of queries: 7
14 Correct 1 ms 208 KB # of queries: 14
15 Correct 1 ms 336 KB # of queries: 81
16 Correct 3 ms 396 KB # of queries: 170
17 Correct 188 ms 4172 KB # of queries: 11124
18 Correct 222 ms 4032 KB # of queries: 11029
19 Correct 184 ms 4160 KB # of queries: 11087
20 Correct 193 ms 3932 KB # of queries: 10416
21 Correct 177 ms 3804 KB # of queries: 9812
22 Correct 202 ms 4196 KB # of queries: 11159
23 Correct 215 ms 4228 KB # of queries: 11139
24 Correct 74 ms 2240 KB # of queries: 5247
25 Correct 201 ms 3988 KB # of queries: 10880
26 Correct 171 ms 3860 KB # of queries: 10176
27 Correct 72 ms 2288 KB # of queries: 5201
28 Correct 68 ms 4288 KB # of queries: 3996
29 Correct 65 ms 4256 KB # of queries: 3992
30 Correct 57 ms 4320 KB # of queries: 3996