| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 458064 |
2021-08-08T00:15:28 Z |
JovanB |
Library (JOI18_library) |
C++17 |
|
246 ms |
560 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
vector <vector <int>> comps;
int query(int n, vector <int> v){
vector <int> s;
for(int i=0; i<n; i++) s.push_back(0);
for(auto c : v) s[c - 1] = 1;
return Query(s);
}
void Solve(int _n){
int n = _n;
comps.push_back({1});
for(int i=2; i<=n; i++){
vector <int> qvr;
for(int j=1; j<=i; j++) qvr.push_back(j);
int nc = query(n, qvr);
if(nc == comps.size() + 1){
comps.push_back({i});
continue;
}
else if(nc == comps.size()){
int k = comps.size();
int l = 0, r = k-1, tr = k;
while(l <= r){
int mid = (l+r)/2;
qvr.clear();
for(int j=0; j<=mid; j++) for(auto c : comps[j]) qvr.push_back(c);
qvr.push_back(i);
if(query(n, qvr) <= mid + 1){
r = mid - 1;
tr = mid;
}
else l = mid + 1;
}
if(comps[tr].size() == 1){
comps[tr].push_back(i);
continue;
}
qvr.clear();
for(int j=0; j+1<comps[tr].size(); j++) qvr.push_back(comps[tr][j]);
qvr.push_back(i);
if(query(n, qvr) == 1) comps[tr].insert(comps[tr].begin(), i);
else comps[tr].push_back(i);
}
else{
int k = comps.size();
int l = 0, r = k-1, t1 = k;
while(l <= r){
int mid = (l+r)/2;
qvr.clear();
for(int j=0; j<=mid; j++) for(auto c : comps[j]) qvr.push_back(c);
qvr.push_back(i);
if(query(n, qvr) <= mid + 1){
r = mid - 1;
t1 = mid;
}
else l = mid + 1;
}
l = 0, r = k-1;
int t2 = k;
while(l <= r){
int mid = (l+r)/2;
qvr.clear();
for(int j=0; j<=mid; j++) for(auto c : comps[j]) qvr.push_back(c);
qvr.push_back(i);
if(query(n, qvr) <= mid){
r = mid - 1;
t2 = mid;
}
else l = mid + 1;
}
qvr.clear();
for(int j=0; j+1<comps[t1].size(); j++) qvr.push_back(comps[t1][j]);
qvr.push_back(i);
if(query(n, qvr) == 1) reverse(comps[t1].begin(), comps[t1].end());
qvr.clear();
for(int j=0; j+1<comps[t2].size(); j++) qvr.push_back(comps[t2][j]);
qvr.push_back(i);
if(query(n, qvr) == 2) reverse(comps[t2].begin(), comps[t2].end());
comps[t1].push_back(i);
comps[t1].insert(comps[t1].end(), comps[t2].begin(), comps[t2].end());
comps.erase(comps.begin() + t2);
}
}
Answer(comps[0]);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if(nc == comps.size() + 1){
| ~~~^~~~~~~~~~~~~~~~~~~
library.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | else if(nc == comps.size()){
| ~~~^~~~~~~~~~~~~~~
library.cpp:44:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int j=0; j+1<comps[tr].size(); j++) qvr.push_back(comps[tr][j]);
| ~~~^~~~~~~~~~~~~~~~~
library.cpp:77:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int j=0; j+1<comps[t1].size(); j++) qvr.push_back(comps[t1][j]);
| ~~~^~~~~~~~~~~~~~~~~
library.cpp:81:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int j=0; j+1<comps[t2].size(); j++) qvr.push_back(comps[t2][j]);
| ~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
200 KB |
# of queries: 1307 |
| 2 |
Correct |
25 ms |
200 KB |
# of queries: 1293 |
| 3 |
Correct |
25 ms |
200 KB |
# of queries: 1367 |
| 4 |
Correct |
26 ms |
200 KB |
# of queries: 1353 |
| 5 |
Correct |
22 ms |
300 KB |
# of queries: 1361 |
| 6 |
Correct |
25 ms |
296 KB |
# of queries: 1342 |
| 7 |
Correct |
25 ms |
300 KB |
# of queries: 1356 |
| 8 |
Correct |
24 ms |
300 KB |
# of queries: 1287 |
| 9 |
Correct |
23 ms |
304 KB |
# of queries: 1362 |
| 10 |
Correct |
15 ms |
320 KB |
# of queries: 804 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
200 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
200 KB |
# of queries: 5 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 10 |
| 15 |
Correct |
1 ms |
200 KB |
# of queries: 55 |
| 16 |
Correct |
2 ms |
200 KB |
# of queries: 117 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
200 KB |
# of queries: 1307 |
| 2 |
Correct |
25 ms |
200 KB |
# of queries: 1293 |
| 3 |
Correct |
25 ms |
200 KB |
# of queries: 1367 |
| 4 |
Correct |
26 ms |
200 KB |
# of queries: 1353 |
| 5 |
Correct |
22 ms |
300 KB |
# of queries: 1361 |
| 6 |
Correct |
25 ms |
296 KB |
# of queries: 1342 |
| 7 |
Correct |
25 ms |
300 KB |
# of queries: 1356 |
| 8 |
Correct |
24 ms |
300 KB |
# of queries: 1287 |
| 9 |
Correct |
23 ms |
304 KB |
# of queries: 1362 |
| 10 |
Correct |
15 ms |
320 KB |
# of queries: 804 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
200 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
200 KB |
# of queries: 5 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 10 |
| 15 |
Correct |
1 ms |
200 KB |
# of queries: 55 |
| 16 |
Correct |
2 ms |
200 KB |
# of queries: 117 |
| 17 |
Correct |
190 ms |
452 KB |
# of queries: 8978 |
| 18 |
Correct |
246 ms |
340 KB |
# of queries: 8911 |
| 19 |
Correct |
219 ms |
348 KB |
# of queries: 8951 |
| 20 |
Correct |
203 ms |
464 KB |
# of queries: 8430 |
| 21 |
Correct |
188 ms |
448 KB |
# of queries: 7889 |
| 22 |
Correct |
210 ms |
560 KB |
# of queries: 9031 |
| 23 |
Correct |
223 ms |
348 KB |
# of queries: 8979 |
| 24 |
Correct |
70 ms |
420 KB |
# of queries: 4132 |
| 25 |
Correct |
218 ms |
460 KB |
# of queries: 8789 |
| 26 |
Correct |
192 ms |
340 KB |
# of queries: 8208 |
| 27 |
Correct |
80 ms |
328 KB |
# of queries: 4123 |
| 28 |
Correct |
78 ms |
336 KB |
# of queries: 2996 |
| 29 |
Correct |
77 ms |
332 KB |
# of queries: 2993 |
| 30 |
Correct |
82 ms |
332 KB |
# of queries: 2996 |
