제출 #953684

#제출 시각아이디문제언어결과실행 시간메모리
953684sysia도서관 (JOI18_library)C++17
100 / 100
231 ms816 KiB
//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]]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...