제출 #1071839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071839		TsotneSV	동굴 (IOI13_cave)	C++17	100 / 100	207 ms	860 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[] = {0,0},paygorn[] = {1,0},n = 2;

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);
    
    if(curr == -1) curr = N; 

    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);
            
            for(int i=0;i<=m;i++) S[idx[i]] = 1 - S[idx[i]];
            
            if(x == -1) x = N;

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

        }
        

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

        int x = tryCombination(S);
        if(x == -1) x = N;

        if(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;
        } 
		
		x = tryCombination(S); if(x == -1) x = N;
        curr = x;
        
        idx.erase(idx.begin()+id);

    } 

    answer(S,D);

}

/*int main() {

    exploreCave(2);

    return 0;
}*/

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