| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 804479 |
2023-08-03T08:59:48 Z |
vjudge1 |
Library (JOI18_library) |
C++14 |
|
51 ms |
508 KB |
#include<bits/stdc++.h>
#include "library.h"
using namespace std ;
const int N = 1000 ;
bool fl[N + 1][N + 1] ;
//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> ans, qr ;
vector<int> 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) ;
}
}
void ultra_clear(int n)
{
for(int i = 0 ; i < n ; i++)
qr[i] = 0 ;
}
void Solve(int n)
{
for(int i = 1 ; i <= n ; i++)
qr.push_back(0) ;
for(int i = 1 ; i <= n ; i++)
{
// cout<<"ksi "<<i<<'\n' ;
int l = 1, r = n ;
// cout<<"abu1\n" ;
while(l < r)
{
int mid = (l + r) >> 1, abu = 0 ;
ultra_clear(n) ;
qr[i - 1] = 1 ;
for(int j = l ; j <= mid ; j++)
{
if(i > mid || i < l)
{
for(int q : v[i])
if(l <= q && q <= mid)
abu++ ;
}
for(int q : v[j])
if(l <= q && q <= mid || q == i)
abu++ ;
qr[j - 1] = 1 ;
}
abu /= 2 ;
if(Query(qr) + abu != (mid - l + 1) + (i > mid || i < l))
r = mid ;
else
l = mid + 1 ;
}
ultra_clear(n) ;
qr[i - 1] = 1 ;
qr[l - 1] = 1 ;
if(!fl[i][l] && Query(qr) == 1)
{
// cout << "1+ " << i << "-" << r << '\n' ;
v[i].push_back(l) ;
v[l].push_back(i) ;
fl[i][l] = 1 ;
fl[l][i] = 1 ;
}
if(l != n)
{
ultra_clear(n) ;
qr[i] = 1 ;
int ks = 0 ;
if(i < l)
{
for(int q : v[i])
if(l <= q)
ks++ ;
}
for(int j = l + 1 ; j <= n ; j++)
{
for(int q : v[j])
if(l <= q || q == i)
ks++ ;
qr[j - 1] = 1 ;
}
if(Query(qr) + ks != n - l + (i < l + 1))
{
// cout << "abu2\n" ;
r = n ;
while(l < r)
{
int mid = (l + r) >> 1, abu = 0 ;
ultra_clear(n) ;
qr[i - 1] = 1 ;
if(i > mid || i < l)
{
for(int q : v[i])
if(l <= q && q <= mid)
abu++ ;
}
for(int j = l ; j <= mid ; j++)
{
for(int q : v[j])
if(l <= q && q <= mid || q == i)
abu++ ;
qr[j - 1] = 1 ;
}
abu /= 2 ;
if(Query(qr) + abu != (mid - l + 1) + (i > mid || i < l))
r = mid ;
else
l = mid + 1 ;
}
ultra_clear(n) ;
qr[i - 1] = 1 ;
qr[l - 1] = 1 ;
if(!fl[i][l] && Query(qr) == 1)
{
// cout<<"2+" << i << "-" << l << '\n' ;
v[i].push_back(l) ;
v[l].push_back(i) ;
fl[i][l] = 1 ;
fl[l][i] = 1 ;
}
}
}
if(l > 1)
{
ultra_clear(n) ;
qr[i] = 1 ;
int ks = 0 ;
for(int q : v[i])
if(q < l)
ks++ ;
for(int j = 1 ; j < l ; j++)
{
for(int q : v[j])
if(q < l || q == i)
ks++ ;
qr[j - 1] = 1 ;
}
ks /= 2 ;
if(Query(qr) + ks != l - 1 + (i >= l))
{
// cout<<"abu3\n" ;
r = l, l = 1 ;
while(l < r)
{
int mid = (l + r) >> 1, abu = 0 ;
ultra_clear(n) ;
qr[i - 1] = 1 ;
if(i > mid || i < l)
{
for(int q : v[i])
if(l <= q && q <= mid)
abu++ ;
}
for(int j = l ; j <= mid ; j++)
{
for(int q : v[j])
if(l <= q && q <= mid || q == i)
abu++ ;
qr[j - 1] = 1 ;
}
abu /= 2 ;
if(Query(qr) + abu != (mid - l + 1) + (i > mid || i < l))
r = mid ;
else
l = mid + 1 ;
}
ultra_clear(n) ;
qr[i - 1] = 1 ;
qr[l - 1] = 1 ;
if(!fl[i][l] && Query(qr) == 1)
{
// cout<<"3+" << i << "-" << l << '\n' ;
v[i].push_back(l) ;
v[l].push_back(i) ;
fl[i][l] = 1 ;
fl[l][i] = 1 ;
}
}
}
}
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 'void Solve(int)':
library.cpp:63:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
63 | if(l <= q && q <= mid || q == i)
| ~~~~~~~^~~~~~~~~~~
library.cpp:120:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
120 | if(l <= q && q <= mid || q == i)
| ~~~~~~~^~~~~~~~~~~
library.cpp:177:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
177 | if(l <= q && q <= mid || q == i)
| ~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
488 KB |
# of queries: 4637 |
| 2 |
Incorrect |
40 ms |
508 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
488 KB |
# of queries: 4637 |
| 2 |
Incorrect |
40 ms |
508 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
