제출 #953684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953684		sysia	도서관 (JOI18_library)	C++17	100 / 100	231 ms	816 KiB

library

//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 / 19
• Subtask 2: 81 / 81