#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
int const nmax = 1000;
int pref[1 + nmax];
int _query(int x, int y, int n){
vector<int> s(n);
s[y - 1] = 1;
for(int i = 0; i < x; i++)
s[i] = 1;
return (x + 1) - Query(s);
}
vector<int> g[1 + nmax];
void addedge(int x, int y){
g[x].push_back(y);
g[y].push_back(x);
}
void extractchain(int node, int parent, vector<int> &sol){
sol.push_back(node);
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h];
if(to != parent)
extractchain(to, node, sol);
}
}
void Solve(int n)
{
for(int i = 1; i <= n; i++){
pref[i] = pref[i - 1];
int x = 0;
for(int jump = (1 << 10); 0 < jump; jump /= 2)
if(x + jump < i && _query(x + jump, i, n) == pref[x + jump])
x += jump;
if(x + 1 < i){
addedge(x + 1, i);
pref[i]++;
x++;
for(int jump = (1 << 10); 0 < jump; jump /= 2)
if(x + jump < i && _query(x + jump, i, n) == 1 + pref[x + jump])
x += jump;
if(x + 1 < i){
addedge(x + 1, i);
pref[i]++;
}
}
}
vector<int> res;
for(int i = 1; i <= n; i++)
if(g[i].size() == 1) {
extractchain(i, 0, res);
break;
}
Answer(res);
}
Compilation message
library.cpp: In function 'void extractchain(int, int, std::vector<int>&)':
library.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
384 KB |
# of queries: 1706 |
| 2 |
Correct |
35 ms |
400 KB |
# of queries: 1749 |
| 3 |
Correct |
43 ms |
632 KB |
# of queries: 1827 |
| 4 |
Correct |
38 ms |
400 KB |
# of queries: 1826 |
| 5 |
Correct |
31 ms |
384 KB |
# of queries: 1814 |
| 6 |
Correct |
36 ms |
384 KB |
# of queries: 1818 |
| 7 |
Correct |
34 ms |
396 KB |
# of queries: 1825 |
| 8 |
Correct |
36 ms |
384 KB |
# of queries: 1712 |
| 9 |
Correct |
36 ms |
384 KB |
# of queries: 1818 |
| 10 |
Correct |
23 ms |
384 KB |
# of queries: 1064 |
| 11 |
Incorrect |
5 ms |
384 KB |
Wrong Answer [4] |
| 12 |
Correct |
4 ms |
384 KB |
# of queries: 1 |
| 13 |
Correct |
5 ms |
384 KB |
# of queries: 4 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 7 |
| 15 |
Correct |
6 ms |
384 KB |
# of queries: 59 |
| 16 |
Correct |
7 ms |
384 KB |
# of queries: 148 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
384 KB |
# of queries: 1706 |
| 2 |
Correct |
35 ms |
400 KB |
# of queries: 1749 |
| 3 |
Correct |
43 ms |
632 KB |
# of queries: 1827 |
| 4 |
Correct |
38 ms |
400 KB |
# of queries: 1826 |
| 5 |
Correct |
31 ms |
384 KB |
# of queries: 1814 |
| 6 |
Correct |
36 ms |
384 KB |
# of queries: 1818 |
| 7 |
Correct |
34 ms |
396 KB |
# of queries: 1825 |
| 8 |
Correct |
36 ms |
384 KB |
# of queries: 1712 |
| 9 |
Correct |
36 ms |
384 KB |
# of queries: 1818 |
| 10 |
Correct |
23 ms |
384 KB |
# of queries: 1064 |
| 11 |
Incorrect |
5 ms |
384 KB |
Wrong Answer [4] |
| 12 |
Correct |
4 ms |
384 KB |
# of queries: 1 |
| 13 |
Correct |
5 ms |
384 KB |
# of queries: 4 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 7 |
| 15 |
Correct |
6 ms |
384 KB |
# of queries: 59 |
| 16 |
Correct |
7 ms |
384 KB |
# of queries: 148 |
| 17 |
Correct |
342 ms |
536 KB |
# of queries: 12128 |
| 18 |
Correct |
294 ms |
656 KB |
# of queries: 11966 |
| 19 |
Correct |
313 ms |
384 KB |
# of queries: 12097 |
| 20 |
Correct |
269 ms |
504 KB |
# of queries: 11275 |
| 21 |
Correct |
253 ms |
504 KB |
# of queries: 10650 |
| 22 |
Correct |
311 ms |
384 KB |
# of queries: 12109 |
| 23 |
Correct |
296 ms |
504 KB |
# of queries: 12141 |
| 24 |
Correct |
131 ms |
504 KB |
# of queries: 5527 |
| 25 |
Correct |
305 ms |
504 KB |
# of queries: 11844 |
| 26 |
Correct |
258 ms |
384 KB |
# of queries: 11061 |
| 27 |
Correct |
98 ms |
384 KB |
# of queries: 5520 |
| 28 |
Correct |
139 ms |
436 KB |
# of queries: 5923 |
| 29 |
Correct |
152 ms |
656 KB |
# of queries: 5915 |
| 30 |
Correct |
154 ms |
608 KB |
# of queries: 5923 |
