#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
return os<<"(" <<p.first<<", "<<p.second<<")"; }
typedef pair<int, int> ii;
template<typename T> using min_pq =
priority_queue<T, vector<T>, greater<T> >;
const int maxn = 10010;
int n;
vector<ii> adj;
vector<int> g[maxn];
int cnt[maxn];
bool has(int l, int r) {
vector<int>v(n);
//debug(l), debug(r);
for(int i=l; i<=r; i++) {
v[i] = 1;
}
for(ii &b : adj) {
if(!v[b.first] or !v[b.second]) continue;
int x, y;
tie(x, y) = b;
if(cnt[x] == 2 or cnt[y] == 2) {
v[cnt[x] == 2 ? x : y] = 0;
} else if(cnt[x] == 1 and cnt[y] == 1) {
v[cnt[x] == 1 ? x : y] = 0;
}
} int c = 0;
//for(int b : v) cout<<b<<' '; cout<<endl;
for(int i=1; i<=n; i++) {
c += v[i-1];
}
if(c == 0) return false;
int ret = Query(v); ret--;
//debug(ret);
if(ret < c - 1) return true;
return false;
}
bool connected(int x, int y) {
vector<int>v(n);
v[x] = v[y] = 1;
int ret = Query(v);
ret--; return !ret;
}
void dfs(int p, int u, vector<int> &v) {
v.push_back(u);
for(int b : g[u]) {
if(b - p) {
dfs(u, b, v);
}
}
}
void Solve(int N) {
n = N;
{
if(n == 1) {
vector<int>temp(n);
temp[0] = 1;
Answer(temp);
}
}
while(adj.size() < n-2) {
int lo = 0, hi = n-1, l, r;
while(lo <= hi) {
int mid = lo + hi >> 1;
int temp = has(0, mid);
//cout<<"["<<0<<","<<mid<<"] = "<<temp<<endl;
if(temp) {
r = mid;
hi = mid-1;
} else {
lo = mid+1;
}
}
lo = 0, hi = r-1;
while(lo <= hi) {
int mid = lo + hi >> 1;
int temp = has(mid, r);
//cout<<"["<<mid<<","<<r<<"] = "<<temp<<endl;
if(temp) {
l = mid;
lo = mid + 1;
} else {
hi = mid-1;
}
}
//cout<<"Found !!!! Done !!!! ====> "<<l<<" *** "<<r<<endl;
adj.push_back(ii(l, r));
cnt[l]++;
cnt[r]++;
}
vector<int> shit;
for(int i=0; i<n; i++)
if(cnt[i] == 1) shit.push_back(i);
sort(all(shit));
if(shit.size() == 4) {
for(int i=0; i<4; i++) {
for(int j=i+1; j<4; j++) {
int x = shit[i], y = shit[j];
if(binary_search(all(adj), ii(x, y)) or binary_search(all(adj), ii(y, x)))
continue;
if(connected(x, y)) {
adj.push_back(ii(x, y));
cnt[x]++, cnt[y]++;
goto hell;
}
}
}
hell : ;
}
else {
int z;
for(int i=0; i<n; i++)
if(cnt[i] == 0)
z = i;
int x = shit[0], y = shit[1];
cnt[x]++;
if(connected(x, z)) {
adj.push_back(ii(x, z));
cnt[x]++;
} else {
adj.push_back(ii(y, z));
cnt[y]++;
}
}
for(ii &b : adj) {
g[b.first].push_back(b.second);
g[b.second].push_back(b.first);
}
vector<int> final;
for(int i=0; i<n; i++) {
if(cnt[i] == 1) {
dfs(-1, i, final);
break;
}
}
/*for(ii &b : adj) {
cout<<"b = "<<"("<<b.first<<","<<b.second<<")"<<endl;
}*/
for(int &b : final) b++;
Answer(final);
}
Compilation message
library.cpp: In function 'int myrand(int, int)':
library.cpp:14:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
^~
library.cpp:14:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
^~~
library.cpp: In function 'void Solve(int)':
library.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(adj.size() < n-2) {
~~~~~~~~~~~^~~~~
library.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
library.cpp:99:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
library.cpp:140:15: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(connected(x, z)) {
~~~~~~~~~^~~~~~
library.cpp:111:8: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
cnt[l]++;
~~~~~^
library.cpp:97:14: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
lo = 0, hi = r-1;
~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
504 KB |
Output is correct |
| 2 |
Correct |
42 ms |
620 KB |
Output is correct |
| 3 |
Correct |
32 ms |
672 KB |
Output is correct |
| 4 |
Correct |
47 ms |
704 KB |
Output is correct |
| 5 |
Correct |
47 ms |
740 KB |
Output is correct |
| 6 |
Correct |
47 ms |
740 KB |
Output is correct |
| 7 |
Correct |
50 ms |
860 KB |
Output is correct |
| 8 |
Correct |
44 ms |
860 KB |
Output is correct |
| 9 |
Correct |
45 ms |
864 KB |
Output is correct |
| 10 |
Correct |
19 ms |
864 KB |
Output is correct |
| 11 |
Runtime error |
2 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
504 KB |
Output is correct |
| 2 |
Correct |
42 ms |
620 KB |
Output is correct |
| 3 |
Correct |
32 ms |
672 KB |
Output is correct |
| 4 |
Correct |
47 ms |
704 KB |
Output is correct |
| 5 |
Correct |
47 ms |
740 KB |
Output is correct |
| 6 |
Correct |
47 ms |
740 KB |
Output is correct |
| 7 |
Correct |
50 ms |
860 KB |
Output is correct |
| 8 |
Correct |
44 ms |
860 KB |
Output is correct |
| 9 |
Correct |
45 ms |
864 KB |
Output is correct |
| 10 |
Correct |
19 ms |
864 KB |
Output is correct |
| 11 |
Runtime error |
2 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
