oj.uz

Submission #414551

# Submission time Handle Problem Language Result Execution time Memory
414551 2021-05-30T16:12:53 Z Runtime_error_ Library (JOI18_library) C++14
0 / 100
 58 ms 296 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){
    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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 292 KB # of queries: 2387
2 Correct 48 ms 200 KB # of queries: 2433
3 Correct 52 ms 200 KB # of queries: 2638
4 Correct 35 ms 288 KB # of queries: 2593
5 Correct 27 ms 296 KB # of queries: 2504
6 Correct 44 ms 292 KB # of queries: 2553
7 Correct 48 ms 200 KB # of queries: 2568
8 Correct 26 ms 292 KB # of queries: 2402
9 Correct 58 ms 200 KB # of queries: 2512
10 Correct 32 ms 200 KB # of queries: 1478
11 Runtime error 1 ms 200 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 292 KB # of queries: 2387
2 Correct 48 ms 200 KB # of queries: 2433
3 Correct 52 ms 200 KB # of queries: 2638
4 Correct 35 ms 288 KB # of queries: 2593
5 Correct 27 ms 296 KB # of queries: 2504
6 Correct 44 ms 292 KB # of queries: 2553
7 Correct 48 ms 200 KB # of queries: 2568
8 Correct 26 ms 292 KB # of queries: 2402
9 Correct 58 ms 200 KB # of queries: 2512
10 Correct 32 ms 200 KB # of queries: 1478
11 Runtime error 1 ms 200 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -