Submission #1071760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071760		TsotneSV	Cave (IOI13_cave)	C++17	0 / 100	105 ms	1116 KiB

cave

#include <bits/stdc++.h>

#include "cave.h"
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/

#define pb push_back
#define ins insert
#define sz(x) ((long long) (x).size())
#define dbg(x) cerr<<#x<<" "<<x<<endl

/*int saygex[] = {1,1,0,1,0,0,1,1},paygorn[] = {3,1,0,2,5,4,7,6},n = 8;

int tryCombination(int S[]) {

    int ans = 1e9;

    for(int i=0;i<n;i++) {
        if(S[i] != saygex[i]) {
            ans = min(ans,paygorn[i]);
        }
    }

    return (ans == 1e9 ? -1 : ans);

}

void answer(int S[], int D[]) {

    for(int i=0;i<n;i++) cout<<S[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++) cout<<D[i]<<" ";
    cout<<endl;
}*/

void exploreCave(int N) {
    
    int S[N],D[N]; memset(S,0,sizeof(S)); int curr = tryCombination(S);

    vector<int> idx; for(int i=0;i<N;i++) idx.pb(i),D[i] = i;

    while(idx.size()) {

        int l = 0,r = sz(idx)-1,id = sz(idx);

        while(l <= r) {

            int m = (l + r)/2;

            for(int i=0;i<=m;i++) S[idx[i]] = 1 - S[idx[i]];
            
            int x = tryCombination(S);

            if(x != curr) {
                id = m;
                r = m - 1;
            }else {
                l = m + 1;
            }

            for(int i=0;i<=m;i++) S[idx[i]] = 1 - S[idx[i]];

        }

        for(int i=0;i<=id;i++) S[idx[i]] = 1 - S[idx[i]];

        int x = tryCombination(S);

        if(x != -1 and x < curr) {
        	for(int i=0;i<=id;i++) S[idx[i]] = 1 - S[idx[i]];
            D[idx[id]] = x;  
        } else {
            D[idx[id]] = curr;
            curr=(x == -1 ? N : x); 
        } 
        
        idx.erase(idx.begin()+id);

    } 

    answer(S,D);

}

/*int main() {

    exploreCave(8);

    return 0;
}*/

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