이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |