Submission #160089

#	Time	Username	Problem	Language	Result	Execution time	Memory
160089		combi1k1	Library (JOI18_library)	C++14	100 / 100	644 ms	408 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81