| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 953684 |
2024-03-26T12:58:34 Z |
sysia |
Library (JOI18_library) |
C++17 |
|
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]]);
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
