| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 994883 |
2024-06-08T08:09:29 Z |
Bula |
Library (JOI18_library) |
C++17 |
|
72 ms |
344 KB |
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int x = 0;
int ask(int l, int r, int idx){
l--, r--; idx--; for(int i = 0; i < p.size(); i++) p[i] = 0;
for(int i = l; i <= r; i++) p[i] = 1;
if(idx != -1) p[idx] = 1;
if(x) p[x - 1] = 0;
return Query(p);
}
void Solve(int n){
p.resize(n);
vector<int> pref(n + 1), suf(n + 1);
for(int i = 1; i <= n; i++){
pref[i] = ask(1, i, 0);
suf[i] = ask(i, n, 0);
}
vector<pair<int, int>> pr(n + 1);
for(int i = 1; i <= n; i++){
int l = 1, r = i - 1;
while(l < r){
int m = (l + r) / 2;
if(ask(1, m, i) == pref[m]) r = m;
else l = m + 1;
}
if(l == r && ask(1, l, i) == pref[l]) pr[i].first = l;
if(!pr[i].first){
l = i + 1, r = n;
while(l < r){
int m = (l + r + 1) / 2;
if(ask(m, n, i) == suf[m]) l = m;
else r = m - 1;
}
if(l == r && ask(l, n, i) == suf[l]) pr[i].first = l;
}
x = pr[i].first;
l = 1, r = i - 1;
while(l < r){
int m = (l + r) / 2;
if(ask(1, m, i) == ask(1, m, 0)) r = m;
else l = m + 1;
}
if(l == r && ask(1, l, i) == ask(1, l, 0)) pr[i].second = l;
if(!pr[i].second){
l = i + 1, r = n;
while(l < r){
int m = (l + r + 1) / 2;
if(ask(m, n, i) == ask(m, n, 0)) l = m;
else r = m - 1;
}
if(l == r && ask(l, n, i) == ask(l, n, 0)) pr[i].second = l;
}
x = 0;
}
int k = 1; vector<int> ans;
for(int i = 1; i <= n; i++){
if(!pr[i].second) k = i;
}
vector<int> vis(n + 1); vis[0] = 1;
while(ans.size() < n){
if(vis[k]) break;
ans.push_back(k); vis[k] = 1;
if(!vis[pr[k].first]){
k = pr[k].first;
}else if(!vis[pr[k].second]){
k = pr[k].second;
}
}
Answer(ans);
}
Compilation message
library.cpp: In function 'int ask(int, int, int)':
library.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | l--, r--; idx--; for(int i = 0; i < p.size(); i++) p[i] = 0;
| ~~^~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:62:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | while(ans.size() < n){
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
344 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
344 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
