oj.uz

Submission #565884

# Submission time Handle Problem Language Result Execution time Memory
565884 2022-05-21T13:41:49 Z InternetPerson10 Library (JOI18_library) C++17
100 / 100
 384 ms 568 KB 
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

vector<vector<int>> nums;

int N;

int ask(vector<int> v) {
    vector<int> q(N, 0);
    for(int i = 0; i < v.size(); i++) {
        if(v[i] == 1) {
            for(int g : nums[i]) q[g] = 1;
        }
    }
    return Query(q);
}

void validCombine(int &x, int &y) {
    vector<int> q(N, 0);
    if(nums[y].size() == 1) swap(x, y);
    if(nums[y].size() == 1) return;
    if(nums[x].size() == 1) {
        q[nums[x][0]] = 1;
        q[nums[y][0]] = 1;
        if(Query(q) == 2) {
            reverse(nums[y].begin(), nums[y].end());
        }
        return;
    }
    q[nums[x][0]] = 1;
    q[nums[x].back()] = 1;
    q[nums[y][0]] = 1;
    if(Query(q) == 3 - (nums[x].size() == 2)) {
        reverse(nums[y].begin(), nums[y].end());
    }
    q.clear();
    q.resize(N, 0);
    q[nums[x].back()] = 1;
    q[nums[y][0]] = 1;
    if(Query(q) == 2) {
        reverse(nums[x].begin(), nums[x].end());
    }
}

void combine(int x, int y) { 
    validCombine(x, y);
    vector<vector<int>> nums2;
    for(int i = 0; i < nums.size(); i++) {
        if(i != x && i != y) nums2.push_back(nums[i]);
    }
    nums2.push_back(nums[x]);
    for(int g : nums[y]) nums2.back().push_back(g);
    nums = nums2;
}

void smallSolve(int n) { // Finds two magkatabi
    if(n == 2) {
        combine(0, 1);
        return;
    }
    vector<int> good(n, 0);
    vector<int> v;
    v.resize(n);
    for(int i = 0; i < n; i++) v[i] = i;
    random_shuffle(v.begin(), v.end());
    for(int i = 0; i < (n+3)/2; i++) good[v[i]] = 1;
    v.clear();
    int x = (n+3)/2;
    while(x != 2) {
        for(int i = 0; i < n; i++) {
            if(good[i]) v.push_back(i);
        }
        int res = (x+1)/2;
        vector<int> test;
        while(res == (x+1)/2) {
            test = good;
            random_shuffle(v.begin(), v.end());
            for(int i = 0; i < x/2; i++) test[v[i]] = 0;
            res = ask(test);
        }
        good = test;
        x = (x+1) / 2;
        v.clear();
    }
    int a = -1, b = -1;
    for(int i = 0; i < n; i++) {
        if(good[i]) {
            a = b;
            b = i;
        }
    }
    combine(a, b);
}

void Solve(int m) {
    N = m;
    srand(time(NULL));
    nums.resize(N);
    for(int i = 0; i < N; i++) nums[i].push_back(i);
    for(int i = N; i > 1; i--) {
        smallSolve(i);
        /*
        for(vector<int> v : nums) {
            for(int g : v) {
                cout << g << ' ';
            }
            cout << '\n';
        }
        cout << "-\n";
        */
    }
    for(int i = 0; i < N; i++) nums[0][i]++;
    Answer(nums[0]);
}

Compilation message

library.cpp: In function 'int ask(std::vector<int>)':
library.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
library.cpp: In function 'void combine(int, int)':
library.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < nums.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 488 KB # of queries: 2610
2 Correct 40 ms 356 KB # of queries: 2486
3 Correct 37 ms 360 KB # of queries: 2704
4 Correct 47 ms 372 KB # of queries: 2696
5 Correct 40 ms 344 KB # of queries: 2861
6 Correct 38 ms 372 KB # of queries: 2685
7 Correct 37 ms 364 KB # of queries: 2775
8 Correct 23 ms 344 KB # of queries: 2556
9 Correct 39 ms 468 KB # of queries: 2761
10 Correct 21 ms 208 KB # of queries: 1597
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 3
14 Correct 0 ms 208 KB # of queries: 4
15 Correct 1 ms 208 KB # of queries: 56
16 Correct 4 ms 208 KB # of queries: 206

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 488 KB # of queries: 2610
2 Correct 40 ms 356 KB # of queries: 2486
3 Correct 37 ms 360 KB # of queries: 2704
4 Correct 47 ms 372 KB # of queries: 2696
5 Correct 40 ms 344 KB # of queries: 2861
6 Correct 38 ms 372 KB # of queries: 2685
7 Correct 37 ms 364 KB # of queries: 2775
8 Correct 23 ms 344 KB # of queries: 2556
9 Correct 39 ms 468 KB # of queries: 2761
10 Correct 21 ms 208 KB # of queries: 1597
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 3
14 Correct 0 ms 208 KB # of queries: 4
15 Correct 1 ms 208 KB # of queries: 56
16 Correct 4 ms 208 KB # of queries: 206
17 Correct 380 ms 424 KB # of queries: 19584
18 Correct 347 ms 456 KB # of queries: 19408
19 Correct 329 ms 544 KB # of queries: 19700
20 Correct 332 ms 420 KB # of queries: 18465
21 Correct 313 ms 412 KB # of queries: 17533
22 Correct 384 ms 548 KB # of queries: 19389
23 Correct 332 ms 456 KB # of queries: 19532
24 Correct 145 ms 524 KB # of queries: 8722
25 Correct 341 ms 420 KB # of queries: 19153
26 Correct 331 ms 568 KB # of queries: 18106
27 Correct 137 ms 416 KB # of queries: 8734
28 Correct 373 ms 432 KB # of queries: 19489
29 Correct 335 ms 424 KB # of queries: 19469
30 Correct 362 ms 424 KB # of queries: 19705