oj.uz

Submission #441576

# Submission time Handle Problem Language Result Execution time Memory
441576 2021-07-05T12:21:17 Z blue Library (JOI18_library) C++17
100 / 100
 383 ms 576 KB 
#include "library.h"
#include <vector>
#include <iostream>
using namespace std;

const int maxN = 1000;
int N1;

int ask_vector(vector<int> Q)
{
    vector<int> M(N1, 0);
    for(int q:Q) M[q-1] = 1;
    return Query(M);
}

vector<int> neighbors[1+maxN];

bool neighboring(int i, int j)
{
    bool flag = 0;
    for(int x: neighbors[i]) if(x == j) flag = 1;
    return flag;
}

void find_neighbors(int I, vector<int> Q, int lo, int hi)
{
    // cerr << "find_neighbors " << I << ", ";
    // for(int q:Q) cerr << q << ' ';
    // cerr << '\n';
    if(Q.size() == 0) return;
    else if(hi == 0) return;
    else if(neighbors[I].size() == 2) return;
    else if(Q.size() == 1)
    {
        if (lo >= 1 || ask_vector(vector<int>{I, Q[0]}) == 1)
        {
            neighbors[I].push_back(Q[0]);
            neighbors[Q[0]].push_back(I);
        }
    }
    else
    {

        vector<int> Q1, Q2;
        for(int i = 0; i < Q.size()/2; i++) Q1.push_back(Q[i]);
        for(int i = Q.size()/2; i < Q.size(); i++) Q2.push_back(Q[i]);

        int noI = ask_vector(Q1);
        Q1.push_back(I);
        int withI = ask_vector(Q1);
        Q1.pop_back();

        int neighbors_of_I = noI - withI + 1;
        find_neighbors(I, Q1, neighbors_of_I, neighbors_of_I);
        find_neighbors(I, Q2, max(0, lo - neighbors_of_I), hi - neighbors_of_I);
    }
}


void Solve(int N)
{
    N1 = N;

    for(int i = 1; i <= N; i++)
    {
        if(neighbors[i].size() == 2) continue;

        vector<int> Q;
        for(int j = 1; j <= N; j++)
        {
            if(i != j && !neighboring(i, j))
                Q.push_back(j);
        }

        find_neighbors(i, Q, 0, 2);
    }

















    vector<int> visit(N+1, 0);

    vector<int> res;
    for(int i = 1; i <= N; i++)
    {
        if(neighbors[i].size() <= 1)
        {
            res.push_back(i);
            visit[i] = 1;
            break;
        }
    }

    for(int i = 0; i < N; i++)
    {
        int u = res[i];
        for(int v: neighbors[u])
        {
            if(visit[v]) continue;
            visit[v] = 1;
            res.push_back(v);
        }
    }


    // for(int r:res) cerr << r << ' ';
    // cerr << '\n';

    for(int r:res) cerr << r << ' ';
    cerr << '\n';
    Answer(res);
}

Compilation message

library.cpp: In function 'void find_neighbors(int, std::vector<int>, int, int)':
library.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i = 0; i < Q.size()/2; i++) Q1.push_back(Q[i]);
      |                        ~~^~~~~~~~~~~~
library.cpp:46:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = Q.size()/2; i < Q.size(); i++) Q2.push_back(Q[i]);
      |                                 ~~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB # of queries: 2660
2 Correct 51 ms 324 KB # of queries: 2692
3 Correct 50 ms 200 KB # of queries: 2786
4 Correct 42 ms 304 KB # of queries: 2840
5 Correct 57 ms 300 KB # of queries: 2798
6 Correct 37 ms 320 KB # of queries: 2818
7 Correct 43 ms 200 KB # of queries: 2836
8 Correct 47 ms 200 KB # of queries: 2700
9 Correct 47 ms 200 KB # of queries: 2800
10 Correct 30 ms 200 KB # of queries: 1606
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 316 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 13
15 Correct 2 ms 200 KB # of queries: 100
16 Correct 5 ms 200 KB # of queries: 234

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB # of queries: 2660
2 Correct 51 ms 324 KB # of queries: 2692
3 Correct 50 ms 200 KB # of queries: 2786
4 Correct 42 ms 304 KB # of queries: 2840
5 Correct 57 ms 300 KB # of queries: 2798
6 Correct 37 ms 320 KB # of queries: 2818
7 Correct 43 ms 200 KB # of queries: 2836
8 Correct 47 ms 200 KB # of queries: 2700
9 Correct 47 ms 200 KB # of queries: 2800
10 Correct 30 ms 200 KB # of queries: 1606
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 316 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 13
15 Correct 2 ms 200 KB # of queries: 100
16 Correct 5 ms 200 KB # of queries: 234
17 Correct 329 ms 352 KB # of queries: 18466
18 Correct 349 ms 448 KB # of queries: 18192
19 Correct 289 ms 336 KB # of queries: 18268
20 Correct 274 ms 344 KB # of queries: 17132
21 Correct 323 ms 344 KB # of queries: 16256
22 Correct 314 ms 468 KB # of queries: 18378
23 Correct 383 ms 468 KB # of queries: 18340
24 Correct 130 ms 328 KB # of queries: 8438
25 Correct 298 ms 576 KB # of queries: 17998
26 Correct 332 ms 576 KB # of queries: 16780
27 Correct 125 ms 332 KB # of queries: 8384
28 Correct 369 ms 468 KB # of queries: 19967
29 Correct 376 ms 448 KB # of queries: 19945
30 Correct 379 ms 472 KB # of queries: 19967