oj.uz

답안 #953684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953684 2024-03-26T12:58:34 Z sysia 도서관 (JOI18_library) C++17
100 / 100
 231 ms 816 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "library.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo = 1e9+7;

void Solve(int n){
	if (n == 1){
		Answer({1});
		return;
	}
	if (n == 2){
		Answer({1, 2});
		return;
	}
	vector<vector<int>>tab(n+1);
	vector<int>where(n+1);
	iota(where.begin(), where.end(), 0);
	for (int i = 1; i<=n; i++) tab[i].emplace_back(i);
	while (1){
		vector<vector<int>>curr;
		for (int i = 1; i<=n; i++) {
			if (!tab[i].empty()){
				curr.emplace_back(vector<int>{tab[i][0]});
				if ((int)tab[i].size() > 1) {
					vector<int>now;
					for (int j = 1; j<(int)tab[i].size(); j++){
						now.emplace_back(tab[i][j]);
					}
					curr.emplace_back(now);
				}
			}
		}
		if (curr.size() <= 2) break;
		debug(curr);
		int s = (int)curr.size();
		int l = 0, r = s-1;
		int f = s-1;
		while (r >= l){
			int m = (l+r)/2;
			//m+1 spojnych dodajemy
			vector<int>M(n);
			int ile = m+1;
			for (int i = 0; i<=m; i++){
				for (auto x: curr[i]){
					M[x-1] = 1;
				}
			}
			for (int i=1; i<=m; i++){
				if (where[curr[i-1].back()] == where[curr[i].back()]){
					ile--;
				}
			}
			if (ile-Query(M) > 0) {
				f = m;
				r = m-1;
			} else l = m+1;
		}
		// debug(f);
		l = 0, r = f;
		int g = 0;
		while (r >= l){
			int m = (l+r)/2;
			vector<int>M(n);
			int ile = f-m+1;
			for (int i = m; i<=f; i++){
				for (auto x: curr[i]){
					M[x-1] = 1;
				}
			}
			for (int i=m+1; i<=f; i++){
				if (where[curr[i-1].back()] == where[curr[i].back()]){
					ile--;
				}
			}
			if (ile-Query(M) == 0){
				r = m-1;;
			} else {
				g = m;
				l = m+1;
			}
		}
		assert(f != oo);
		// debug(g, f, curr[g], curr[f]);

		//zmergowac te dwie spojne tymi koncami
		int a = curr[g].back();
		int b = curr[f].back();
		int A = where[a];
		int B = where[b];
		if ((int)tab[A].size() < (int)tab[B].size()) {
			swap(a, b);
			swap(A, B);
		}
		if (tab[A].back() != a) {
			reverse(tab[A].begin(), tab[A].end());
		}
		if (tab[B][0] != b){
			reverse(tab[B].begin(), tab[B].end());
		}
		debug(a, b, tab[A], tab[B]);
		for (auto x: tab[B]){
			where[x] = A;
			tab[A].emplace_back(x);
		}
		debug(tab[A]);
		tab[B].clear();
		// break;
	}
	debug(tab[where[1]]);
	Answer(tab[where[1]]);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 460 KB # of queries: 2326
2 Correct 16 ms 628 KB # of queries: 2300
3 Correct 19 ms 468 KB # of queries: 2435
4 Correct 18 ms 460 KB # of queries: 2450
5 Correct 19 ms 464 KB # of queries: 2438
6 Correct 21 ms 464 KB # of queries: 2430
7 Correct 23 ms 464 KB # of queries: 2409
8 Correct 19 ms 464 KB # of queries: 2328
9 Correct 25 ms 464 KB # of queries: 2432
10 Correct 15 ms 456 KB # of queries: 1419
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 356 KB # of queries: 8
14 Correct 0 ms 344 KB # of queries: 12
15 Correct 1 ms 344 KB # of queries: 88
16 Correct 1 ms 344 KB # of queries: 199

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 460 KB # of queries: 2326
2 Correct 16 ms 628 KB # of queries: 2300
3 Correct 19 ms 468 KB # of queries: 2435
4 Correct 18 ms 460 KB # of queries: 2450
5 Correct 19 ms 464 KB # of queries: 2438
6 Correct 21 ms 464 KB # of queries: 2430
7 Correct 23 ms 464 KB # of queries: 2409
8 Correct 19 ms 464 KB # of queries: 2328
9 Correct 25 ms 464 KB # of queries: 2432
10 Correct 15 ms 456 KB # of queries: 1419
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 356 KB # of queries: 8
14 Correct 0 ms 344 KB # of queries: 12
15 Correct 1 ms 344 KB # of queries: 88
16 Correct 1 ms 344 KB # of queries: 199
17 Correct 207 ms 556 KB # of queries: 16657
18 Correct 209 ms 556 KB # of queries: 16401
19 Correct 231 ms 560 KB # of queries: 16574
20 Correct 203 ms 548 KB # of queries: 15505
21 Correct 170 ms 540 KB # of queries: 14619
22 Correct 216 ms 552 KB # of queries: 16624
23 Correct 221 ms 556 KB # of queries: 16629
24 Correct 74 ms 508 KB # of queries: 7541
25 Correct 191 ms 556 KB # of queries: 16211
26 Correct 178 ms 548 KB # of queries: 15160
27 Correct 74 ms 496 KB # of queries: 7531
28 Correct 130 ms 564 KB # of queries: 10490
29 Correct 126 ms 816 KB # of queries: 10478
30 Correct 132 ms 568 KB # of queries: 10490