Submission #45465

#	Time	Username	Problem	Language	Result	Execution time	Memory
45465		Extazy	Library (JOI18_library)	C++17	0 / 100	199 ms	880 KiB

library

#include <bits/stdc++.h>
#include "library.h"
#ifdef skeleta
    #include "grader.cpp"
#endif

using namespace std;

const int MAXN = 1007;

int n;
vector < int > v[MAXN];
vector < pair < int, int > > p;
int questions_count;
bool used[MAXN];
queue < int > q;
vector < int > ans;

void Solve(int N) {
    int i,j;
    vector < int > qry;
    
    n=N;

    for(i=1;i<=n;i++) {
        used[i]=false;
        v[i].clear();
    }
    ans.clear();
    questions_count=0;
    p.clear();

    qry.assign(n,0);

    for(i=1;i<=n;i++) {
        for(j=i+1;j<=n;j++) {
            p.push_back(make_pair(i,j));
        }
    }

    random_shuffle(p.begin(),p.end());

    for(i=0;i<(int)(p.size()) && questions_count<20000;i++) {
        if(v[p[i].first].size()==2 || v[p[i].second].size()==2) continue;
        
        qry[p[i].first-1]=1;
        qry[p[i].second-1]=1;
       
        ++questions_count;

        if(Query(qry)==1) {
            v[p[i].first].push_back(p[i].second);
            v[p[i].second].push_back(p[i].first);
        }

        qry[p[i].first-1]=0;
        qry[p[i].second-1]=0;
    }

    assert(questions_count<20000);

    for(i=1;i<=n;i++) if(v[i].size()==1) {
        used[i]=true;
        q.push(i);
        break;
    }

    while(!q.empty()) {
        int curr=q.front();
        q.pop();
        
        ans.push_back(curr);

        for(i=0;i<(int)(v[curr].size());i++) if(!used[v[curr][i]]) {
            used[v[curr][i]]=true;
            q.push(v[curr][i]);
        }
    }

    Answer(ans);
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81