oj.uz

Submission #438107

# Submission time Handle Problem Language Result Execution time Memory
438107 2021-06-27T14:59:36 Z blue Library (JOI18_library) C++17
0 / 100
 58 ms 444 KB 
#include "library.h"
#include <vector>
#include <iostream>
using namespace std;

const int maxN = 1000;
int N1;

vector<int> neighbors[1+maxN];

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

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

void search_neighbors(int a, vector<int> Q, int s)
{
    if(Q.size() == s)
    {
        for(int y:Q)
        {
            if(ask(vector<int>{a, y}) == 1)
            {
                neighbors[a].push_back(y);
                neighbors[y].push_back(a);
            }
        }
        return;
    }

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

    Q.clear();



    int ask1 = ask(Q1);
    Q1.push_back(a);
    int ask2 = ask(Q1);
    Q1.pop_back();

    int q1_neighbors = 1 - (ask2 - ask1);

    if(q1_neighbors == 0)
    {
        search_neighbors(a, Q2, s);
    }
    else if(q1_neighbors == s)
    {
        search_neighbors(a, Q1, s);
    }
    else
    {
        search_neighbors(a, Q1, 1);
        search_neighbors(a, Q2, 1);
    }


    //ask1 - ask2 + 1 == number of neighbors of a in Q1

    //neighbors in Q1 == 2 => ask2 = ask1 - 1
    //neighbors in Q1 == 1 => ask2 = ask1
    //neighbors in Q1 == 0 => ask2 = ask1 + 1
}

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) continue;
            if(neighboring(i, j) || neighbors[j].size() == 2) continue;
            Q.push_back(j);
        }
        search_neighbors(i, Q, 2 - neighbors[i].size());
    }

    // for(int i = 1; i <= N; i++)
    // {
    //     cerr << i << ": ";
    //     for(int j: neighbors[i]) cerr << j << ' ';
    //     cerr << '\n';
    // }

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


    Answer(res);
}

Compilation message

library.cpp: In function 'void search_neighbors(int, std::vector<int>, int)':
library.cpp:27:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     if(Q.size() == s)
      |        ~~~~~~~~~^~~~
library.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < Q.size()/2; i++)
      |                    ~~^~~~~~~~~~~~
library.cpp:45:31: 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 = Q.size()/2; i < Q.size(); i++)
      |                             ~~^~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 444 KB # of queries: 2507
2 Correct 46 ms 316 KB # of queries: 2520
3 Correct 48 ms 328 KB # of queries: 2619
4 Correct 48 ms 320 KB # of queries: 2679
5 Correct 53 ms 324 KB # of queries: 2675
6 Correct 28 ms 316 KB # of queries: 2627
7 Correct 58 ms 320 KB # of queries: 2683
8 Correct 50 ms 320 KB # of queries: 2574
9 Correct 41 ms 328 KB # of queries: 2670
10 Correct 38 ms 300 KB # of queries: 1516
11 Runtime error 1 ms 200 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 444 KB # of queries: 2507
2 Correct 46 ms 316 KB # of queries: 2520
3 Correct 48 ms 328 KB # of queries: 2619
4 Correct 48 ms 320 KB # of queries: 2679
5 Correct 53 ms 324 KB # of queries: 2675
6 Correct 28 ms 316 KB # of queries: 2627
7 Correct 58 ms 320 KB # of queries: 2683
8 Correct 50 ms 320 KB # of queries: 2574
9 Correct 41 ms 328 KB # of queries: 2670
10 Correct 38 ms 300 KB # of queries: 1516
11 Runtime error 1 ms 200 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -