oj.uz

Submission #311276

# Submission time Handle Problem Language Result Execution time Memory
311276 2020-10-09T20:15:47 Z LucaDantas Library (JOI18_library) C++17
100 / 100
 520 ms 512 KB 
#include <cstdio>
#include <vector>
#include <cassert>
#include<algorithm>
#include "library.h"
using namespace std;

#define pb push_back
#define sz(a) (int)((a).size())

vector<vector<int>> grp;

void Solve(int n)
{
	for(int i = 0; i < n; i++)
		grp.pb({i});

	while(sz(grp) > 1) {
		vector<vector<int>> dir, esq;
		vector<vector<int>> grande = grp;
		do {
			esq.clear();
			dir.clear();
			vector<int> qr(n);
			for(int i = 0; i < sz(grande)/2; i++)
				esq.pb(grande[i]);
			
			for(int i = sz(grande)/2; i < sz(grande); i++)
				dir.pb(grande[i]);

			for(auto x : esq)
				for(auto y : x)
					qr[y] = 1;

			if(Query(qr) < sz(esq)) grande = esq;
			else {
				fill(qr.begin(), qr.end(), 0);
				for(auto x : dir)
					for(auto y : x)
						qr[y] = 1;

				if(Query(qr) < sz(dir)) grande = dir;
				else {
					while(sz(esq) + sz(dir) > 2) {
						vector<vector<int>> l1, l2, r1, r2;
						
						for(int i = 0; i < sz(dir)/2; i++)
							r1.pb(dir[i]);
						
						for(int i = sz(dir)/2; i < sz(dir); i++)
							r2.pb(dir[i]);

						for(int i = 0; i < sz(esq)/2; i++)
							l1.pb(esq[i]);

						for(int i = sz(esq)/2; i < sz(esq); i++)
							l2.pb(esq[i]);
						

						fill(qr.begin(), qr.end(), 0);
						for(auto x : esq)
							for(auto y : x)
								qr[y] = 1;

						for(auto x : r1)
							for(auto y : x)
								qr[y] = 1;

						if(Query(qr) < sz(esq) + sz(r1)) dir = r1;
						else dir = r2;
						
						fill(qr.begin(), qr.end(), 0);
						for(auto x : l1)
							for(auto y : x)
								qr[y] = 1;
						
						for(auto x : dir)
							for(auto y : x)
								qr[y] = 1;

						if(Query(qr) < sz(l1) + sz(dir)) esq = l1;
						else esq = l2;
					}
				}
			}
		} while(sz(esq) + sz(dir) > 2);

		assert(sz(dir) == 1 && sz(esq) == 1);

		auto find = [&](vector<int>& achar) {
			for(int i = 0; i < sz(grp); i++) {
				if(grp[i].front() == achar.front()) return i;
				if(grp[i].front() == achar.back()) {reverse(grp[i].begin(), grp[i].end()); return i;}
			}
			assert(0);
			return -1;
		};

		auto apagar = [&](int pos) {
			swap(grp.back(), grp[pos]);
			grp.pop_back();
		};

		for(int cnt = 0; cnt < 2; cnt++, swap(esq[0], dir[0])) {
			vector<int> qr(n);
			qr[esq[0].back()] = 1;
			qr[dir[0].front()] = 1;
			if(Query(qr) == 2)
				reverse(dir[0].begin(), dir[0].end());
			else break;

			fill(qr.begin(), qr.end(), 0);
			qr[esq[0].back()] = 1;
			qr[dir[0].front()] = 1;
			if(Query(qr) == 2)
				reverse(esq[0].begin(), esq[0].end());
			else break;

			fill(qr.begin(), qr.end(), 0);
			qr[esq[0].back()] = 1;
			qr[dir[0].front()] = 1;
			if(Query(qr) == 2)
				reverse(dir[0].begin(), dir[0].end());
			else break;

			fill(qr.begin(), qr.end(), 0);
			qr[esq[0].back()] = 1;
			qr[dir[0].front()] = 1;
			if(Query(qr) == 1) break;
		}

		apagar(find(dir[0]));
		int id = find(esq[0]);
		for(auto add : dir[0])
			grp[id].pb(add);
	}

	for(int i = 0; i < n; i++)
		grp[0][i]++;
	printf("\n");
	Answer(grp[0]);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 384 KB # of queries: 2540
2 Correct 42 ms 384 KB # of queries: 2513
3 Correct 45 ms 384 KB # of queries: 2641
4 Correct 44 ms 384 KB # of queries: 2617
5 Correct 49 ms 288 KB # of queries: 2649
6 Correct 44 ms 384 KB # of queries: 2641
7 Correct 47 ms 384 KB # of queries: 2639
8 Correct 42 ms 384 KB # of queries: 2488
9 Correct 38 ms 384 KB # of queries: 2616
10 Correct 30 ms 384 KB # of queries: 1560
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 3
13 Correct 1 ms 256 KB # of queries: 10
14 Correct 1 ms 256 KB # of queries: 13
15 Correct 2 ms 256 KB # of queries: 111
16 Correct 5 ms 256 KB # of queries: 208

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 384 KB # of queries: 2540
2 Correct 42 ms 384 KB # of queries: 2513
3 Correct 45 ms 384 KB # of queries: 2641
4 Correct 44 ms 384 KB # of queries: 2617
5 Correct 49 ms 288 KB # of queries: 2649
6 Correct 44 ms 384 KB # of queries: 2641
7 Correct 47 ms 384 KB # of queries: 2639
8 Correct 42 ms 384 KB # of queries: 2488
9 Correct 38 ms 384 KB # of queries: 2616
10 Correct 30 ms 384 KB # of queries: 1560
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 3
13 Correct 1 ms 256 KB # of queries: 10
14 Correct 1 ms 256 KB # of queries: 13
15 Correct 2 ms 256 KB # of queries: 111
16 Correct 5 ms 256 KB # of queries: 208
17 Correct 487 ms 512 KB # of queries: 17641
18 Correct 488 ms 512 KB # of queries: 17449
19 Correct 485 ms 512 KB # of queries: 17715
20 Correct 468 ms 512 KB # of queries: 16476
21 Correct 396 ms 512 KB # of queries: 15544
22 Correct 520 ms 512 KB # of queries: 17672
23 Correct 495 ms 512 KB # of queries: 17510
24 Correct 159 ms 384 KB # of queries: 8049
25 Correct 479 ms 512 KB # of queries: 17168
26 Correct 421 ms 512 KB # of queries: 16046
27 Correct 157 ms 384 KB # of queries: 8009
28 Correct 363 ms 512 KB # of queries: 12415
29 Correct 377 ms 512 KB # of queries: 12402
30 Correct 334 ms 512 KB # of queries: 12415