Submission #45180

# Submission time Handle Problem Language Result Execution time Memory
45180 2018-04-11T16:34:18 Z ikura355 Library (JOI18_library) C++14
100 / 100
499 ms 716 KB
#include "library.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int n;
int vis[maxn];
vector<int> vec, ans;
int link(int st) {
    vector<int> a;
    vis[st] = 1;
    for(int i=1;i<=n;i++) if(!vis[i]) a.push_back(i);
    int l = 0, r = a.size()-1;
    while(l<r) {
        //ask
        int mid = (l+r)/2;
        for(int i=l;i<=mid;i++) vec[a[i]-1] = 1;
        int bef = Query(vec);
        vec[st-1] = 1;
        int aft = Query(vec);
        //reset
        for(int i=l;i<=mid;i++) vec[a[i]-1] = 0;
        vec[st-1] = 0;
        //divide
        if(bef==aft) r = mid;
        else l = mid+1;
    }
//    printf("%d -> %d\n",st,a[l]);
    return a[l];
}
void Solve(int N) {
    n = N;
    if(n==1) return Answer({1});
    vec.clear(); ans.clear();
    memset(vis,0,sizeof(vis));
    //1000
    int st = -1;
    for(int i=0;i<n;i++) vec.push_back(0);
    for(int x=1;x<=n;x++) {
        for(int i=1;i<=n;i++) vec[i-1] = (x!=i);
        if(Query(vec)==1) st = x;
    }
    ans.push_back(st);
    //1000 * 10
    for(int i=0;i<n;i++) vec[i] = 0;
    for(int i=1;i<n;i++) ans.push_back(link(ans[i-1]));
    Answer(ans);
}
# Verdict Execution time Memory Grader output
1 Correct 42 ms 248 KB Output is correct
2 Correct 40 ms 308 KB Output is correct
3 Correct 40 ms 384 KB Output is correct
4 Correct 40 ms 428 KB Output is correct
5 Correct 46 ms 448 KB Output is correct
6 Correct 61 ms 448 KB Output is correct
7 Correct 46 ms 492 KB Output is correct
8 Correct 30 ms 496 KB Output is correct
9 Correct 47 ms 512 KB Output is correct
10 Correct 29 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 4 ms 520 KB Output is correct
16 Correct 3 ms 520 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 42 ms 248 KB Output is correct
2 Correct 40 ms 308 KB Output is correct
3 Correct 40 ms 384 KB Output is correct
4 Correct 40 ms 428 KB Output is correct
5 Correct 46 ms 448 KB Output is correct
6 Correct 61 ms 448 KB Output is correct
7 Correct 46 ms 492 KB Output is correct
8 Correct 30 ms 496 KB Output is correct
9 Correct 47 ms 512 KB Output is correct
10 Correct 29 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 4 ms 520 KB Output is correct
16 Correct 3 ms 520 KB Output is correct
17 Correct 484 ms 652 KB Output is correct
18 Correct 455 ms 652 KB Output is correct
19 Correct 457 ms 652 KB Output is correct
20 Correct 433 ms 700 KB Output is correct
21 Correct 360 ms 700 KB Output is correct
22 Correct 444 ms 700 KB Output is correct
23 Correct 499 ms 700 KB Output is correct
24 Correct 171 ms 700 KB Output is correct
25 Correct 450 ms 716 KB Output is correct
26 Correct 473 ms 716 KB Output is correct
27 Correct 157 ms 716 KB Output is correct
28 Correct 450 ms 716 KB Output is correct
29 Correct 408 ms 716 KB Output is correct
30 Correct 489 ms 716 KB Output is correct