Submission #1310752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310752		theiulius	Cave (IOI13_cave)	C++20	0 / 100	2095 ms	836 KiB

cave

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
#include "cave.h"
int t = 1;
int n = 0;

// void answer(int a[], int b[]){
//     for (int i = 0; i < n; i++){
//         cout << a[i] << " ";
//     }
//     cout << endl;
//     for (int i = 0; i < n; i++){
//         cout << b[i] << " ";
//     }
//     cout << endl;
// }

// int tryCombination(int s[]){
//     for (int i = 0; i < n; i++){
//         cout << s[i] << " ";
//     }
//     cout << endl;
//     int x;
//     cin >> x;
//     return x;
// }

void exploreCave(int N) {
    n = N;
    map<int, int> mp;
    int a[n] = {}, b[n] = {};
    for (int i = 0; i < n; i++){ // karebebs gadavuyvebit
        for (int j = 0; j < n; j++){ // berketebi
            if (mp[j]) continue;
            a[j] = 0;
        }
        int x = tryCombination(a), berk = 0; // berketebi
        if (x > i || x == -1){ // sadgac berketi i karistvis gaxsnilia
            berk = 0;
        }else{
            berk = 1;
        }
        // cout << i << "     " << a[i] << endl;
        
        vector<int> unused;
        for (int j = 0; j < n; j++){
            if (!mp[j]){
                unused.pb(j);
            }
        }
        
        int l = 0, r = unused.size() - 1, ans = 0; // berkets vedzebt
        while (l <= r){
            int mid = (l + r) / 2;
            for (int j = 0; j <= mid; j++){
                a[unused[j]] = berk;
            }
            for (int j = mid + 1; j < unused.size(); j++){
                a[unused[j]] = 1 ^ berk;
            }
            x = tryCombination(a);
            
            if (x > i || x == -1){
                r = mid - 1;
                ans = mid;
            }else{
                l = mid + 1;
            }
        }
        ans = unused[ans];
        
        // cout << ans << " " << i << endl;
        b[ans] = i;
        mp[ans] = 1;
        a[ans] = berk;
    }
    
    answer(a, b);
}

// main(){
//     exploreCave(5);
// }

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