oj.uz

Submission #160089

# Submission time Handle Problem Language Result Execution time Memory
160089 2019-10-26T01:53:28 Z combi1k1 Library (JOI18_library) C++14
100 / 100
 644 ms 408 KB 
#include<bits/stdc++.h>
#include "library.h"

using namespace std;

vector<int> ASK;
vector<int> vis;

/*void Answer(vector<int> v)  {
    if (v.size() != Ori.size()) {
        cout << "WRONG ANSWER [4]\n";
        return;
    }
    if (v != Ori)   reverse(v.begin(),v.end());
    if (v != Ori)   cout << "WRONG ANSWER [8]\n";
}*/
int ask(vector<int> v)  {
    if (v.size() == 0)  return  0;
    if (v.size() == 1)  return  1;

    for(int &x : ASK)   x = 0;
    for(int &x : v)     ASK[x - 1] = 1;

    return  Query(ASK);
}
int Connected(int u,vector<int> v)  {
    int a = ask(v); v.push_back(u);
    int b = ask(v); return  a - b + 1;
}

void Solve(int n)   {
    if (n == 1) {   Answer({1});    return; }
    if (n == 2) {   Answer({1,2});  return; }

    ASK.resize(n);
    vis.resize(n);

    queue <int> que;
    vector<int> res;

    for(int i = 1 ; i <= n ; ++i)   {
        vector<int> v;
        for(int j = 1 ; j <= n ; ++j)
            if (j != i) v.push_back(j);
        if (ask(v) == 1)    {
            que.push(i);
            break;
        }
    }
    for(int i = 1 ; i <= n ; ++i)   {
        int u = que.front();
        que.pop();
        res.push_back(u);
        vis[u - 1] = 1;

        if (res.size() == n)    {
            Answer(res);
            return;
        }

        vector<int> v;

        for(int j = 0 ; j < n ; ++j)
            if(!vis[j]) v.push_back(j + 1);

        int l = 1;
        int r = v.size();

        for(; l < r ;)  {
            int m = (l + r) / 2;
            if (Connected(u,vector<int>(v.begin(),v.begin() + m)))
                r = m;
            else
                l = m + 1;
        }
        que.push(v[l - 1]);
    }
}
/*int main()  {
    ios_base::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);

    Ori = {5,2,7,8,4,1,3,9,6};
    Pos = {5,1,6,4,0,8,2,3,7};  Solve(9);   return  0;

    srand(time(NULL));

    for(int t = 0 ; t < 100 ; ++t)  {
        int x;  cin >> x;
        int n = rand() % 10 + 1;
        Ori.resize(n);
        Pos.resize(n);
        iota(Ori.begin(),Ori.end(),1);
        random_shuffle(Ori.begin(),Ori.end());

        for(int i = 0 ; i < n ; ++i)    Pos[Ori[i] - 1] = i;

        cout << n << " : "; for(int x : Ori)    cout << x << " ";
        cout << "\n";

        Solve(n);
    }
}*/

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (res.size() == n)    {
             ~~~~~~~~~~~^~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 404 KB # of queries: 2374
2 Correct 36 ms 408 KB # of queries: 2422
3 Correct 51 ms 376 KB # of queries: 2630
4 Correct 35 ms 316 KB # of queries: 2583
5 Correct 52 ms 248 KB # of queries: 2491
6 Correct 53 ms 248 KB # of queries: 2542
7 Correct 37 ms 400 KB # of queries: 2558
8 Correct 33 ms 248 KB # of queries: 2392
9 Correct 42 ms 376 KB # of queries: 2506
10 Correct 28 ms 248 KB # of queries: 1471
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 3 ms 248 KB # of queries: 0
13 Correct 2 ms 248 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 5
15 Correct 3 ms 296 KB # of queries: 69
16 Correct 5 ms 248 KB # of queries: 181

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 404 KB # of queries: 2374
2 Correct 36 ms 408 KB # of queries: 2422
3 Correct 51 ms 376 KB # of queries: 2630
4 Correct 35 ms 316 KB # of queries: 2583
5 Correct 52 ms 248 KB # of queries: 2491
6 Correct 53 ms 248 KB # of queries: 2542
7 Correct 37 ms 400 KB # of queries: 2558
8 Correct 33 ms 248 KB # of queries: 2392
9 Correct 42 ms 376 KB # of queries: 2506
10 Correct 28 ms 248 KB # of queries: 1471
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 3 ms 248 KB # of queries: 0
13 Correct 2 ms 248 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 5
15 Correct 3 ms 296 KB # of queries: 69
16 Correct 5 ms 248 KB # of queries: 181
17 Correct 644 ms 376 KB # of queries: 17996
18 Correct 554 ms 252 KB # of queries: 17219
19 Correct 550 ms 376 KB # of queries: 17442
20 Correct 450 ms 332 KB # of queries: 16263
21 Correct 451 ms 248 KB # of queries: 15348
22 Correct 543 ms 248 KB # of queries: 17600
23 Correct 565 ms 376 KB # of queries: 17162
24 Correct 179 ms 376 KB # of queries: 7877
25 Correct 620 ms 376 KB # of queries: 17106
26 Correct 416 ms 248 KB # of queries: 15976
27 Correct 181 ms 328 KB # of queries: 7981
28 Correct 503 ms 248 KB # of queries: 16937
29 Correct 515 ms 376 KB # of queries: 16918
30 Correct 584 ms 248 KB # of queries: 16937