Submission #1070818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070818		dosts	Cave (IOI13_cave)	C++17	100 / 100	421 ms	880 KiB

cave

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50;
 
void exploreCave(int32_t N) {
    vector<pii> fix;
    int R[N],D[N];
    for (int i=0;i<N;i++) {
        int S[N];
        for (int j=0;j<N;j++) S[j] = 0;
        for (auto it : fix) {
            S[it.ff] = it.ss;
        }
        int real = tryCombination(S);
            if (real == -1) real = N;
        int l = 1;
        int r = N;
        if (real == i) {
            while (l<=r) {
                int m = (l+r) >> 1;
                int SS[N];
                for (int j=0;j<m;j++) SS[j] = S[j]^1;
                for (int j=m;j<N;j++) SS[j] = S[j];
                for (auto it : fix) SS[it.ff] = it.ss;
                int test = tryCombination(SS);
                if (test == -1) test = N;
                if (test > real) {
                    r = m-1;
                }
                else l = m+1;
            }
        }
        else {
            while (l<=r) {
                int m = (l+r) >> 1;
                int SS[N];
                for (int j=0;j<m;j++) SS[j] = S[j]^1;
                for (int j=m;j<N;j++) SS[j] = S[j];
                for (auto it : fix) SS[it.ff] = it.ss;
                int test = tryCombination(SS);
                if (test == -1) test = N;
                if (test == i) {
                    r = m-1;
                }
                else l = m+1;
            }     
        }
        if (real > i) fix.push_back({l-1,0});
        else fix.push_back({l-1,1});
        R[fix.back().ff] = i;
        D[fix.back().ff] = fix.back().ss;
    }
    answer(D,R);
}

Compilation message (stderr)

cave.cpp:12:29: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | const int MOD = 1e9+7,inf = 2e18;
      |                             ^~~~

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