#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#define vi vector<int>
int n;
int qu(vector<int>& fi, vector<vi>& se, int l, int r) { //eliminate unnecessary copying with &
//stnadard query stuff
vi guess(n);
for (int i = 0; i < n; i++) guess[i] = 0;
for (int val : fi) guess[val-1] = 1;
for (int i = l; i <= r; i++) {
vi vc = se[i];
for (int val : vc) guess[val-1] = 1; //1-index them
}
return Query(guess);
}
vi inds; //store the indices
int nummelds = 0; //debugging tool if needed
void go(vi& le, vector<vi>& stuff, int l, int r) {
if (l == r) {
if (qu(le, stuff, l, r) == 1) {
//good thing
inds.push_back(l);
}
return;
}
if (qu(le, stuff, l, r) == (r-l + 2)) {
return; //this is bad stuff
}
int mid = (l+r)/2;
go(le, stuff, l, mid);
go(le, stuff, mid+1, r);
}
// pintvec(vi& v1) {
// for (int val : v1) cout << val << " ";
// }
vector<vi> rec(int l, int r) {
//this is the modified merge sort type thing
vector<vector<int>> ans; //everything will be copied at most log n times
if (l == r) {
vi cur;
cur.push_back(l);
ans.push_back(cur);
return ans;
}
int mid = (l+r)/2;
vector<vi> le = rec(l, mid);
vector<vi> re = rec(mid+1, r);
for (int i = le.size()-1; i >= 0; i--) {
vi vc = le[i];
int cur = qu(vc, re, 0, re.size()-1);
if (cur == re.size()+1) continue;
inds.clear(); //just store the meld indices
go(vc, re, 0, re.size()-1);
vi nv; //new vector;
vi bef; //put before my boy
vi aft; //put after my boy
vi tmp; //temporary stuff
vector<vi> tp2;
if (inds.size() == 2) {
if (re[inds[0]].size() < re[inds[1]].size()) {
swap(inds[0], inds[1]);
}
}
for (int j = 0; j < inds.size(); j++) {
int ic = inds[j]; //get the value
// cout << "unioning ";
// pintvec(vc);
// cout << " to ";
// pintvec(re[ic]);
tmp.clear();
tmp.push_back(vc[0]);
if (bef.size() == 0 &&
qu(tmp, re, ic, ic) == 1) { //only 1 group
//we know it is before me
//if it is size one just make the first before
//see which end meld
// cout << " (type bef)";
tmp.clear();
tmp.push_back(re[ic][0]);
tp2.clear();
tp2.push_back(tmp);
if (re[ic].size() == 1 || qu(vc, tp2, 0, 0) == 1) {
//first guy is linked
// cout << " go first";
for (int k = re[ic].size()-1; k >= 0; k--) {
bef.push_back(re[ic][k]);
}
}
else {
// cout << "go second";
for (int k = 0; k < re[ic].size(); k++) {
bef.push_back(re[ic][k]);
}
}
}
else {
// cout << "(type aft)";
tmp.clear();
tmp.push_back(re[ic][0]);
tp2.clear();
tp2.push_back(tmp);
if (re[ic].size() == 1 || qu(vc, tp2, 0, 0) == 1) {
//first guy is linked
// cout << " go first";
for (int k = 0; k < re[ic].size(); k++) {
aft.push_back(re[ic][k]);
}
}
else {
// cout << " go second";
for (int k = re[ic].size()-1; k >= 0; k--) {
aft.push_back(re[ic][k]);
}
}
}
//cout << endl;
}
// cout << "before unions: ";
// pintvec(vc);
// cout << " and then ";
for (int val : bef) {
nv.push_back(val);
}
for (int val : vc) {
nv.push_back(val);
}
for (int val : aft) {
nv.push_back(val);
}
// pintvec(nv);
// cout << endl;
sort(inds.begin(), inds.end());
reverse(inds.begin(), inds.end());
for (int cur : inds) {
re.erase(re.begin()+cur);
}
//erase the used vector
re.push_back(nv);
le.erase(le.begin()+i); //take it out afterwards
}
for (vi vc : le) ans.push_back(vc);
for (vi vc : re) ans.push_back(vc);
return ans;
}
void Solve(int N)
{
n = N;
vector<vi> res = rec(1, n);
assert(res.size() == 1);
// cout << "my ans: ";
// for (int val : res[0]) cout << val << " ";
// cout << endl;
Answer(res[0]);
}
Compilation message
library.cpp: In function 'std::vector<std::vector<int> > rec(int, int)':
library.cpp:62:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cur == re.size()+1) continue;
~~~~^~~~~~~~~~~~~~
library.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < inds.size(); j++) {
~~^~~~~~~~~~~~~
library.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < re[ic].size(); k++) {
~~^~~~~~~~~~~~~~~
library.cpp:125:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < re[ic].size(); k++) {
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
376 KB |
Output is correct |
| 2 |
Correct |
31 ms |
376 KB |
Output is correct |
| 3 |
Correct |
53 ms |
428 KB |
Output is correct |
| 4 |
Correct |
51 ms |
496 KB |
Output is correct |
| 5 |
Correct |
39 ms |
496 KB |
Output is correct |
| 6 |
Correct |
55 ms |
496 KB |
Output is correct |
| 7 |
Correct |
52 ms |
560 KB |
Output is correct |
| 8 |
Correct |
39 ms |
560 KB |
Output is correct |
| 9 |
Correct |
49 ms |
572 KB |
Output is correct |
| 10 |
Correct |
24 ms |
572 KB |
Output is correct |
| 11 |
Correct |
2 ms |
572 KB |
Output is correct |
| 12 |
Correct |
2 ms |
572 KB |
Output is correct |
| 13 |
Correct |
3 ms |
572 KB |
Output is correct |
| 14 |
Correct |
2 ms |
572 KB |
Output is correct |
| 15 |
Correct |
3 ms |
572 KB |
Output is correct |
| 16 |
Correct |
7 ms |
572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
376 KB |
Output is correct |
| 2 |
Correct |
31 ms |
376 KB |
Output is correct |
| 3 |
Correct |
53 ms |
428 KB |
Output is correct |
| 4 |
Correct |
51 ms |
496 KB |
Output is correct |
| 5 |
Correct |
39 ms |
496 KB |
Output is correct |
| 6 |
Correct |
55 ms |
496 KB |
Output is correct |
| 7 |
Correct |
52 ms |
560 KB |
Output is correct |
| 8 |
Correct |
39 ms |
560 KB |
Output is correct |
| 9 |
Correct |
49 ms |
572 KB |
Output is correct |
| 10 |
Correct |
24 ms |
572 KB |
Output is correct |
| 11 |
Correct |
2 ms |
572 KB |
Output is correct |
| 12 |
Correct |
2 ms |
572 KB |
Output is correct |
| 13 |
Correct |
3 ms |
572 KB |
Output is correct |
| 14 |
Correct |
2 ms |
572 KB |
Output is correct |
| 15 |
Correct |
3 ms |
572 KB |
Output is correct |
| 16 |
Correct |
7 ms |
572 KB |
Output is correct |
| 17 |
Correct |
675 ms |
576 KB |
Output is correct |
| 18 |
Correct |
703 ms |
576 KB |
Output is correct |
| 19 |
Correct |
627 ms |
576 KB |
Output is correct |
| 20 |
Correct |
477 ms |
708 KB |
Output is correct |
| 21 |
Correct |
463 ms |
708 KB |
Output is correct |
| 22 |
Correct |
610 ms |
824 KB |
Output is correct |
| 23 |
Correct |
637 ms |
824 KB |
Output is correct |
| 24 |
Correct |
190 ms |
824 KB |
Output is correct |
| 25 |
Correct |
544 ms |
824 KB |
Output is correct |
| 26 |
Correct |
467 ms |
824 KB |
Output is correct |
| 27 |
Correct |
219 ms |
824 KB |
Output is correct |
| 28 |
Correct |
100 ms |
824 KB |
Output is correct |
| 29 |
Correct |
113 ms |
824 KB |
Output is correct |
| 30 |
Correct |
109 ms |
824 KB |
Output is correct |
