제출 #1152786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152786		Esgeer	동굴 (IOI13_cave)	C++20	100 / 100	191 ms	588 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
//#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp <<' '<<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second
const int mod = 998244353;
const int inf = 1e12;
const int N = 70005;

int found[N];
int connected[N];
int toTry[N];
int allZero[N];
void exploreCave(int32_t n) {
    F(i, 0, n) found[i] = -1;
    F(di, 0, n) {
        F(i, 0, n) if(found[i] != -1) {
            allZero[i] = found[i];
        } else {
            allZero[i] = 0;
        }
        int initial = tryCombination(allZero);

        deque<int> possible;
        F(i, 0, n) if(found[i] == -1) possible.pb(i);

        while(possible.size() > 1) {
            int m = possible.size() >> 1;
            F(i, 0, n) if(found[i] != -1) {
                toTry[i] = found[i];
            } else toTry[i] = 0;
            F(i, 0, m) toTry[possible[i]] = 1;

            int ret = tryCombination(toTry);

            if((initial == di && ret != di) || (initial != di && ret == di)) { // the door was altered
                int ps = possible.size();
                F(i, m, ps) possible.pop_back();
            } else {
                F(i, 0, m) possible.pop_front();
            }
        }

        found[possible[0]] = (initial == di);
        connected[possible[0]] = di;
    }
    answer(found, connected);
}

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

cave.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   27 | const int inf = 1e12;
      |                 ^~~~

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