oj.uz

답안 #565871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
565871 2022-05-21T13:21:38 Z InternetPerson10 도서관 (JOI18_library) C++17
19 / 100
 465 ms 432 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);
}

bool validCombine(int x, int y) {
    vector<int> q(N, 0);
    q[nums[x].back()] = 1;
    q[nums[y][0]] = 1;
    return (Query(q) == 1);
}

void combine(int x, int y) { 
    bool ok = validCombine(x, y);
    if(!ok) {
        reverse(nums[x].begin(), nums[x].end());
        ok = validCombine(x, y);
    }
    if(!ok) {
        reverse(nums[y].begin(), nums[y].end());
        ok = validCombine(x, y);
    }
    if(!ok) {
        reverse(nums[x].begin(), nums[x].end());
    }
    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, 1);
    vector<int> v;
    int x = n;
    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;
        }
    }
    if(min(a, b) == -1) {
        while(true) {}
    }
    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:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < nums.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 340 KB # of queries: 2775
2 Correct 48 ms 348 KB # of queries: 2746
3 Correct 49 ms 336 KB # of queries: 2962
4 Correct 44 ms 344 KB # of queries: 3100
5 Correct 41 ms 352 KB # of queries: 2900
6 Correct 32 ms 348 KB # of queries: 3146
7 Correct 46 ms 336 KB # of queries: 3068
8 Correct 46 ms 332 KB # of queries: 2942
9 Correct 58 ms 352 KB # of queries: 3095
10 Correct 31 ms 332 KB # of queries: 1771
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 1
13 Correct 1 ms 208 KB # of queries: 3
14 Correct 1 ms 208 KB # of queries: 5
15 Correct 2 ms 208 KB # of queries: 85
16 Correct 6 ms 208 KB # of queries: 227

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 340 KB # of queries: 2775
2 Correct 48 ms 348 KB # of queries: 2746
3 Correct 49 ms 336 KB # of queries: 2962
4 Correct 44 ms 344 KB # of queries: 3100
5 Correct 41 ms 352 KB # of queries: 2900
6 Correct 32 ms 348 KB # of queries: 3146
7 Correct 46 ms 336 KB # of queries: 3068
8 Correct 46 ms 332 KB # of queries: 2942
9 Correct 58 ms 352 KB # of queries: 3095
10 Correct 31 ms 332 KB # of queries: 1771
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 1
13 Correct 1 ms 208 KB # of queries: 3
14 Correct 1 ms 208 KB # of queries: 5
15 Correct 2 ms 208 KB # of queries: 85
16 Correct 6 ms 208 KB # of queries: 227
17 Runtime error 465 ms 432 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -