| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805406 |
2023-08-03T16:26:33 Z |
vjudge1 |
Library (JOI18_library) |
C++14 |
|
51 ms |
332 KB |
#include<bits/stdc++.h>
#include"library.h"
using namespace std ;
const int N = 1e3 ;
//int Query(vector<int>& v)
//{
// int num ;
// cout << "? " ;
// for(int i : v)
// cout << i << ' ' ;
// cout << '\n' ;
// cin >> num ;
// return num ;
//}
//void Answer(vector<int>& res)
//{
// cout << "! " ;
// for(int i : res)
// cout << i << ' ' ;
// exit(0) ;
//}
vector<int> qr, ans, v[N + 1] ;
void dfs(int city, int last)
{
ans.push_back(city) ;
for(int i : v[city])
{
if(i == last)
continue ;
dfs(i, city) ;
}
}
int get_kol(vector<int> qr)
{
int l = 0, r = 0, kol = 0 ;
for(int i = 0 ; i < qr.size() ; i++)
if(qr[i])
{
if(!l)l = i + 1 ;
r = i + 1 ;
}
for(int i = 0 ; i < qr.size() ; i++)
{
if(!qr[i])
continue ;
for(int j : v[i + 1])
if(l <= j && j <= r)
kol++ ;
}
return kol / 2 ;
}
void Solve(int n)
{
for(int i = 1 ; i <= n ; i++)
qr.push_back(0) ;
for(int i = 1 ; i < n ; i++)
{
int l1 = 0, r1 = n + 1, l2 = 0, r2 ;
bool flag = 0 ;
while(l1 + 1 < r1)
{
int mid = (l1 + r1) >> 1, num ;
for(int j = 1 ; j <= mid ; j++)
qr[j - 1] = 1 ;
num = get_kol(qr) ;
// cout<<"1+ "<<l1<<' '<<r1 << ' ' << num <<'\n' ;
if(Query(qr) != mid - get_kol(qr))
r1 = mid ;
else
l1 = mid ;
for(int j = 1 ; j <= mid ; j++)
qr[j - 1] = 0 ;
}
r2 = r1 ;
while(l2 + 1 < r2)
{
int mid = (l2 + r2) >> 1, num ;
for(int j = mid ; j <= r1 ; j++)
qr[j - 1] = 1 ;
num = get_kol(qr) ;
// cout<<"2+ "<<l2<<' '<<r2 << ' ' << num <<'\n' ;
if(Query(qr) != (r1 - mid + 1) - get_kol(qr))
l2 = mid ;
else
r2 = mid ;
for(int j = mid ; j <= r1 ; j++)
qr[j - 1] = 0 ;
}
// cout << l2 << '-' << r1 << '\n' ;
v[l2].push_back(r1) ;
v[r1].push_back(l2) ;
}
for(int i = 1 ; i <= n ; i++)
if(v[i].size() == 1)
{
dfs(i, 0) ;
break ;
}
Answer(ans) ;
}
//signed main()
//{
// int n ;
// cin >> n ;
// Solve(n) ;
// return 0 ;
//}
Compilation message
library.cpp: In function 'int get_kol(std::vector<int>)':
library.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0 ; i < qr.size() ; i++)
| ~~^~~~~~~~~~~
library.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0 ; i < qr.size() ; i++)
| ~~^~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:62:39: warning: variable 'num' set but not used [-Wunused-but-set-variable]
62 | int mid = (l1 + r1) >> 1, num ;
| ^~~
library.cpp:77:39: warning: variable 'num' set but not used [-Wunused-but-set-variable]
77 | int mid = (l2 + r2) >> 1, num ;
| ^~~
library.cpp:59:14: warning: unused variable 'flag' [-Wunused-variable]
59 | bool flag = 0 ;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
308 KB |
# of queries: 2797 |
| 2 |
Correct |
35 ms |
324 KB |
# of queries: 2784 |
| 3 |
Correct |
39 ms |
320 KB |
# of queries: 2931 |
| 4 |
Correct |
31 ms |
308 KB |
# of queries: 2935 |
| 5 |
Correct |
42 ms |
316 KB |
# of queries: 2936 |
| 6 |
Correct |
51 ms |
308 KB |
# of queries: 2938 |
| 7 |
Correct |
41 ms |
332 KB |
# of queries: 2924 |
| 8 |
Correct |
37 ms |
312 KB |
# of queries: 2791 |
| 9 |
Correct |
38 ms |
208 KB |
# of queries: 2926 |
| 10 |
Correct |
23 ms |
208 KB |
# of queries: 1719 |
| 11 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [4] |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
308 KB |
# of queries: 2797 |
| 2 |
Correct |
35 ms |
324 KB |
# of queries: 2784 |
| 3 |
Correct |
39 ms |
320 KB |
# of queries: 2931 |
| 4 |
Correct |
31 ms |
308 KB |
# of queries: 2935 |
| 5 |
Correct |
42 ms |
316 KB |
# of queries: 2936 |
| 6 |
Correct |
51 ms |
308 KB |
# of queries: 2938 |
| 7 |
Correct |
41 ms |
332 KB |
# of queries: 2924 |
| 8 |
Correct |
37 ms |
312 KB |
# of queries: 2791 |
| 9 |
Correct |
38 ms |
208 KB |
# of queries: 2926 |
| 10 |
Correct |
23 ms |
208 KB |
# of queries: 1719 |
| 11 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [4] |
| 12 |
Halted |
0 ms |
0 KB |
- |
