oj.uz

Submission #45466

# Submission time Handle Problem Language Result Execution time Memory
45466 2018-04-14T08:43:35 Z Extazy Library (JOI18_library) C++17
19 / 100
 504 ms 4776 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) {
    if(N==1) {
        vector < int > ans;
        ans.push_back(1);
        Answer(ans);
        return;
    }

    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;
    }

    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
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 632 KB Output is correct
2 Correct 147 ms 692 KB Output is correct
3 Correct 134 ms 768 KB Output is correct
4 Correct 162 ms 836 KB Output is correct
5 Correct 151 ms 836 KB Output is correct
6 Correct 153 ms 884 KB Output is correct
7 Correct 152 ms 908 KB Output is correct
8 Correct 145 ms 908 KB Output is correct
9 Correct 149 ms 908 KB Output is correct
10 Correct 63 ms 908 KB Output is correct
11 Correct 1 ms 908 KB Output is correct
12 Correct 1 ms 908 KB Output is correct
13 Correct 2 ms 908 KB Output is correct
14 Correct 2 ms 908 KB Output is correct
15 Correct 2 ms 908 KB Output is correct
16 Correct 3 ms 908 KB Output is correct

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 632 KB Output is correct
2 Correct 147 ms 692 KB Output is correct
3 Correct 134 ms 768 KB Output is correct
4 Correct 162 ms 836 KB Output is correct
5 Correct 151 ms 836 KB Output is correct
6 Correct 153 ms 884 KB Output is correct
7 Correct 152 ms 908 KB Output is correct
8 Correct 145 ms 908 KB Output is correct
9 Correct 149 ms 908 KB Output is correct
10 Correct 63 ms 908 KB Output is correct
11 Correct 1 ms 908 KB Output is correct
12 Correct 1 ms 908 KB Output is correct
13 Correct 2 ms 908 KB Output is correct
14 Correct 2 ms 908 KB Output is correct
15 Correct 2 ms 908 KB Output is correct
16 Correct 3 ms 908 KB Output is correct
17 Incorrect 504 ms 4776 KB Wrong Answer [4]
18 Halted 0 ms 0 KB -