oj.uz

Submission #414552

# Submission time Handle Problem Language Result Execution time Memory
414552 2021-05-30T16:14:59 Z Runtime_error_ Library (JOI18_library) C++14
100 / 100
 567 ms 320 KB 
#include <bits/stdc++.h>
#include "library.h"
#define mid (l+r)/2
#define pb push_back
#define mp make_pair
using namespace std;
int n;

int GetNext(int cur,vector<int> &PotentialNext){
    vector<int> Next;
    for(int i=0;i<n;i++)
        if(PotentialNext[i] == 1)
            Next.pb(i);

    if(Next.size() == 1)
        return Next[0];
    int l = 0,r = Next.size()-1;
    while(r!=l){
        vector<int> Left(n,0);
        for(int i=l;i<=mid;i++)
            Left[ Next[i] ] = 1;
        int without = Query(Left);
        Left[cur] = 1;
        int with = Query(Left);
        if(without == with )//then cur is adjacent with one element from the first half
            r = mid;                //because when adding cur the answer is still the same
        else
            l = mid+1;
    }
    return Next[l];
}

void Solve(int N){
    if(N == 1)
        return void(Answer({1}));
    n = N;
    vector<int> ask(n,1),ret;

    //N queries
    for(int i=0;i<n;i++){
        ask[i] = 0;
        if(Query(ask) == 1){
            ret.pb(i);
            break;
        }
        ask[i] = 1;
    }
    //the remaining number is deceasing by one every time so it is 2*sum(log2(i)) 1<=i<=n-1
    for(int i=1;i<n;i++){
        //now excluding the previous elements the i-the element is only adjacent with element i+1
        int cur = GetNext(ret.back(),ask);
        ask[cur] = 0;
        ret.pb(cur);
    }

    for(auto &o:ret)
        ++o;

    Answer(ret);

}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 200 KB # of queries: 2387
2 Correct 39 ms 200 KB # of queries: 2433
3 Correct 43 ms 200 KB # of queries: 2638
4 Correct 50 ms 200 KB # of queries: 2593
5 Correct 46 ms 200 KB # of queries: 2504
6 Correct 29 ms 292 KB # of queries: 2553
7 Correct 28 ms 296 KB # of queries: 2568
8 Correct 46 ms 200 KB # of queries: 2402
9 Correct 47 ms 200 KB # of queries: 2512
10 Correct 21 ms 200 KB # of queries: 1478
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 73
16 Correct 3 ms 200 KB # of queries: 187

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 200 KB # of queries: 2387
2 Correct 39 ms 200 KB # of queries: 2433
3 Correct 43 ms 200 KB # of queries: 2638
4 Correct 50 ms 200 KB # of queries: 2593
5 Correct 46 ms 200 KB # of queries: 2504
6 Correct 29 ms 292 KB # of queries: 2553
7 Correct 28 ms 296 KB # of queries: 2568
8 Correct 46 ms 200 KB # of queries: 2402
9 Correct 47 ms 200 KB # of queries: 2512
10 Correct 21 ms 200 KB # of queries: 1478
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 73
16 Correct 3 ms 200 KB # of queries: 187
17 Correct 523 ms 288 KB # of queries: 18008
18 Correct 496 ms 288 KB # of queries: 17231
19 Correct 548 ms 292 KB # of queries: 17451
20 Correct 453 ms 320 KB # of queries: 16277
21 Correct 406 ms 300 KB # of queries: 15362
22 Correct 450 ms 284 KB # of queries: 17617
23 Correct 539 ms 292 KB # of queries: 17170
24 Correct 159 ms 280 KB # of queries: 7885
25 Correct 520 ms 296 KB # of queries: 17118
26 Correct 451 ms 200 KB # of queries: 15989
27 Correct 194 ms 200 KB # of queries: 7994
28 Correct 567 ms 292 KB # of queries: 17935
29 Correct 498 ms 200 KB # of queries: 17915
30 Correct 535 ms 200 KB # of queries: 17935