Submission #565884

#	Time	Username	Problem	Language	Result	Execution time	Memory
565884		InternetPerson10	Library (JOI18_library)	C++17	100 / 100	384 ms	568 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81