제출 #550603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550603		Olympia	동굴 (IOI13_cave)	C++17	0 / 100	1 ms	424 KiB

cave

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <map>
#include <complex>
#include <cmath>
#include <set>
#include "cave.h"
using namespace std;
vector<bool> oracle = {true, true, false, true};
vector<int> door = {3, 1, 0, 2};
int n = 4;
int tryCombination(bool v[]) {
    vector<int> doors;
    for (int i = 0; i < n; i++) {
        if (v[i] == oracle[i]) {
            doors.push_back(door[i]);
        }
    }
    sort(doors.begin(), doors.end());
    for (int i = 0; i < doors.size(); i++) {
        if (doors[i] != i) {
            return i;
        }
    }
    return doors.size();
}
vector<pair<int,bool>> vec;
void fill (bool v[]) {
    for (auto& p: vec) {
        v[p.first] = p.second;
    }
}
/*
void exploreCave (int n) {
    bool c[n]; int arr[n];
    for (int i = 0; i < n; i++) {
        vector<bool> a;
        a.assign(n, true);
        fill(a);
        bool b = (tryCombination(a) >= i + 1);
        int l = 0;
        int r = n - 1;
        while (l != r) {
            int m = (l + r)/2;
            a.assign(n, !b);
            for (int j = 0; j <= m; j++) {
                a[j] = b;
            }
            fill(a);
            if (tryCombination(a) >= i + 1) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        //cout << i << " " << l << '\n';
        arr[l] = i;
        vec.emplace_back(l, b);
    }
    answer(c, arr);
}
 */

void exploreCave (int N) {
    assert(oracle.size() == door.size());
    int c[N]; int arr[N];
    for (int i = 0; i < n; i++) {
        bool a[n];
        for (int j = 0; j < n; j++) a[j] = true;
        fill(a);
        bool b = (tryCombination(a) >= i + 1);
        int l = 0;
        int r = n - 1;
        while (l != r) {
            int m = (l + r)/2;
            for (int j = 0; j < n; j++) a[j] = !b;
            for (int j = 0; j <= m; j++) {
                a[j] = b;
            }
            fill(a);
            if (tryCombination(a) >= i + 1) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        arr[l] = i;
        vec.emplace_back(l, b);
    }
    for (auto& p: vec) {
        c[p.first] = p.second;
    }
    answer(c, arr);
}

컴파일 시 표준 에러 (stderr) 메시지

cave.cpp: In function 'int tryCombination(bool*)':
cave.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < doors.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24