oj.uz

Submission #45465

# Submission time Handle Problem Language Result Execution time Memory
45465 2018-04-14T08:42:13 Z Extazy Library (JOI18_library) C++17
0 / 100
 199 ms 880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 632 KB Output is correct
2 Correct 140 ms 696 KB Output is correct
3 Correct 138 ms 728 KB Output is correct
4 Correct 156 ms 744 KB Output is correct
5 Correct 199 ms 804 KB Output is correct
6 Correct 158 ms 804 KB Output is correct
7 Correct 159 ms 876 KB Output is correct
8 Correct 166 ms 880 KB Output is correct
9 Correct 161 ms 880 KB Output is correct
10 Correct 63 ms 880 KB Output is correct
11 Incorrect 2 ms 880 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 632 KB Output is correct
2 Correct 140 ms 696 KB Output is correct
3 Correct 138 ms 728 KB Output is correct
4 Correct 156 ms 744 KB Output is correct
5 Correct 199 ms 804 KB Output is correct
6 Correct 158 ms 804 KB Output is correct
7 Correct 159 ms 876 KB Output is correct
8 Correct 166 ms 880 KB Output is correct
9 Correct 161 ms 880 KB Output is correct
10 Correct 63 ms 880 KB Output is correct
11 Incorrect 2 ms 880 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -