| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 344075 |
2021-01-05T05:58:44 Z |
Kerim |
Library (JOI18_library) |
C++17 |
|
432 ms |
748 KB |
#include <cstdio>
#include <vector>
#include "library.h"
#define pb(x) push_back(x)
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define N 1003
using namespace std;
int val[N],n;
vector<int>adj[N],res;
void add(int x,int y){
//printf("%d %d\n",x,y);
adj[x].pb(y);
adj[y].pb(x);
}
void dfs(int nd,int pr){
res.pb(nd);
tr(it,adj[nd])
if(*it!=pr)
dfs(*it,nd);
}
int ask(int x,int i,int effect){
vector<int>M;
int cur=0;
for(int j=0;j<n;j++){
if(j>=x and j<=i)
cur+=val[j],M.pb(1);
else
M.pb(0);
}
//printf("ask %d %d %d %d %d\n",x,i,effect,(Query(M)+cur<=i-x-effect),cur);
return (Query(M)+cur<=i-x-effect);
}
void Solve(int nn){n=nn;
if(n==1){
res.pb(1);
Answer(res);
return;
}
for(int i=1;i<n;i++){
int st=0,en=i-1,a=-1,b=-1;
while(st+1<en){
int mid=(st+en)>>1;
if(ask(mid,i,0))
st=mid;
else
en=mid;
}
if(ask(en,i,0))
st=en;
if(ask(st,i,0)){
add(st+1,i+1);a=st;
en=st-1;st=0;
if(st<=en){
//printf("%d %d %d\n",st,en,i);
while(st+1<en){
int mid=(st+en)>>1;
if(ask(mid,i,1))
st=mid;
else
en=mid;
}
if(ask(en,i,1))
st=en;
if(ask(st,i,1))
add(st+1,i+1),b=st;
}
}
if(~a)val[a]++;
if(~b)val[b]++;
}
for(int i=1;i<=n;i++)
if(adj[i].size()==1){
dfs(i,-1);
break;
}
Answer(res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
364 KB |
# of queries: 2438 |
| 2 |
Correct |
33 ms |
364 KB |
# of queries: 2465 |
| 3 |
Correct |
36 ms |
512 KB |
# of queries: 2581 |
| 4 |
Correct |
43 ms |
364 KB |
# of queries: 2625 |
| 5 |
Correct |
39 ms |
364 KB |
# of queries: 2602 |
| 6 |
Correct |
39 ms |
364 KB |
# of queries: 2583 |
| 7 |
Correct |
35 ms |
364 KB |
# of queries: 2611 |
| 8 |
Correct |
28 ms |
408 KB |
# of queries: 2500 |
| 9 |
Correct |
42 ms |
536 KB |
# of queries: 2560 |
| 10 |
Correct |
27 ms |
364 KB |
# of queries: 1502 |
| 11 |
Correct |
0 ms |
364 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
364 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
384 KB |
# of queries: 4 |
| 14 |
Correct |
1 ms |
364 KB |
# of queries: 11 |
| 15 |
Correct |
2 ms |
364 KB |
# of queries: 93 |
| 16 |
Correct |
4 ms |
364 KB |
# of queries: 209 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
364 KB |
# of queries: 2438 |
| 2 |
Correct |
33 ms |
364 KB |
# of queries: 2465 |
| 3 |
Correct |
36 ms |
512 KB |
# of queries: 2581 |
| 4 |
Correct |
43 ms |
364 KB |
# of queries: 2625 |
| 5 |
Correct |
39 ms |
364 KB |
# of queries: 2602 |
| 6 |
Correct |
39 ms |
364 KB |
# of queries: 2583 |
| 7 |
Correct |
35 ms |
364 KB |
# of queries: 2611 |
| 8 |
Correct |
28 ms |
408 KB |
# of queries: 2500 |
| 9 |
Correct |
42 ms |
536 KB |
# of queries: 2560 |
| 10 |
Correct |
27 ms |
364 KB |
# of queries: 1502 |
| 11 |
Correct |
0 ms |
364 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
364 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
384 KB |
# of queries: 4 |
| 14 |
Correct |
1 ms |
364 KB |
# of queries: 11 |
| 15 |
Correct |
2 ms |
364 KB |
# of queries: 93 |
| 16 |
Correct |
4 ms |
364 KB |
# of queries: 209 |
| 17 |
Correct |
398 ms |
748 KB |
# of queries: 16984 |
| 18 |
Correct |
386 ms |
540 KB |
# of queries: 16692 |
| 19 |
Correct |
409 ms |
420 KB |
# of queries: 16831 |
| 20 |
Correct |
332 ms |
492 KB |
# of queries: 15670 |
| 21 |
Correct |
349 ms |
492 KB |
# of queries: 14857 |
| 22 |
Correct |
393 ms |
748 KB |
# of queries: 16803 |
| 23 |
Correct |
374 ms |
620 KB |
# of queries: 16911 |
| 24 |
Correct |
168 ms |
492 KB |
# of queries: 7893 |
| 25 |
Correct |
352 ms |
492 KB |
# of queries: 16575 |
| 26 |
Correct |
322 ms |
544 KB |
# of queries: 15397 |
| 27 |
Correct |
175 ms |
492 KB |
# of queries: 7742 |
| 28 |
Runtime error |
432 ms |
676 KB |
Execution killed with signal 13 (could be triggered by violating memory limits) |
| 29 |
Halted |
0 ms |
0 KB |
- |
