oj.uz

Submission #160087

# Submission time Handle Problem Language Result Execution time Memory
160087 2019-10-26T01:48:11 Z combi1k1 Library (JOI18_library) C++14
19 / 100
 653 ms 592 KB 
#include<bits/stdc++.h>
#include "library.h"

using namespace std;

vector<int> ASK;
vector<int> Ori;
vector<int> Pos;

/*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);

    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();
        int x = u;
        if (res.size() >= 1)    x = res.back();    res.push_back(u);
        if (res.size() == n)    {
            Answer(res);
            return;
        }

        vector<int> v;

        for(int j = 1 ; j <= n ; ++j)
            if (j != u && j != x)   v.push_back(j);

        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:54:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if (res.size() >= 1)    x = res.back();    res.push_back(u);
         ^~
library.cpp:54:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if (res.size() >= 1)    x = res.back();    res.push_back(u);
                                                    ^~~
library.cpp:55: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 62 ms 376 KB # of queries: 2931
2 Correct 42 ms 316 KB # of queries: 2973
3 Correct 55 ms 316 KB # of queries: 3204
4 Correct 70 ms 252 KB # of queries: 3149
5 Correct 66 ms 328 KB # of queries: 3070
6 Correct 52 ms 296 KB # of queries: 3133
7 Correct 54 ms 376 KB # of queries: 3138
8 Correct 42 ms 420 KB # of queries: 2968
9 Correct 61 ms 248 KB # of queries: 3094
10 Correct 31 ms 376 KB # of queries: 1822
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 0
13 Correct 2 ms 376 KB # of queries: 3
14 Correct 2 ms 376 KB # of queries: 6
15 Correct 3 ms 376 KB # of queries: 104
16 Correct 5 ms 248 KB # of queries: 253

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 376 KB # of queries: 2931
2 Correct 42 ms 316 KB # of queries: 2973
3 Correct 55 ms 316 KB # of queries: 3204
4 Correct 70 ms 252 KB # of queries: 3149
5 Correct 66 ms 328 KB # of queries: 3070
6 Correct 52 ms 296 KB # of queries: 3133
7 Correct 54 ms 376 KB # of queries: 3138
8 Correct 42 ms 420 KB # of queries: 2968
9 Correct 61 ms 248 KB # of queries: 3094
10 Correct 31 ms 376 KB # of queries: 1822
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 0
13 Correct 2 ms 376 KB # of queries: 3
14 Correct 2 ms 376 KB # of queries: 6
15 Correct 3 ms 376 KB # of queries: 104
16 Correct 5 ms 248 KB # of queries: 253
17 Incorrect 653 ms 472 KB Wrong Answer [3]
18 Correct 653 ms 592 KB # of queries: 19991
19 Incorrect 626 ms 424 KB Wrong Answer [3]
20 Correct 592 ms 424 KB # of queries: 18945
21 Correct 489 ms 420 KB # of queries: 17858
22 Incorrect 629 ms 340 KB Wrong Answer [3]
23 Correct 607 ms 456 KB # of queries: 19990
24 Correct 233 ms 376 KB # of queries: 9281
25 Correct 629 ms 376 KB # of queries: 19840
26 Correct 586 ms 248 KB # of queries: 18599
27 Correct 232 ms 376 KB # of queries: 9432
28 Correct 628 ms 464 KB # of queries: 19926
29 Correct 634 ms 384 KB # of queries: 19904
30 Correct 587 ms 344 KB # of queries: 19926