| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 458063 |
2021-08-08T00:12:56 Z |
JovanB |
Library (JOI18_library) |
C++17 |
|
29 ms |
292 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[t1].begin(), comps[t1].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 |
Incorrect |
29 ms |
292 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
292 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
