Submission #1139040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139040		davele	Cave (IOI13_cave)	C++20	0 / 100	184 ms	576 KiB

cave

#ifndef davele
#include "cave.h"
#endif // davele

#include <bits/stdc++.h>
#define pq priority_queue
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(i) (1ll<<(i))
#define next __next
#define pos __pos
using namespace std;
const double PI = acos(-1);
/*const int mod = ;

void sub (int&a, const int&b){
    a-=b;
    if (a<0) a+=mod;
}

void mul (int&a, const int&b){
    a = (1ll*a*b)%mod;
}

void add (int&a, const int&b){
    a+=b;
    if (a>=mod) a-=mod;
}*/

bool minimize (ll&a, const ll&b){
    if (a<=b) return false;
    a=b;
    return true;
}

bool maximize (ll&a, const ll&b){
    if (a>=b) return false;
    a=b;
    return true;
}
////////////////////////////////////////////////////////////////////////////////////////////

bool vis[5005];
int locat[5005], stat[5005];

void exploreCave(int n) {
    /* ... */
    memset(locat, 0, sizeof(locat));
    memset(stat, 0, sizeof(stat));
    memset(vis, false, sizeof(vis));
    for (int i=0; i<n; i++){
        vector <int> rem;
        for (int j=0; j<n; j++) if (vis[j]==false) rem.pb(j);
        for (int x:rem) stat[x] = 0;
        int curkey = 0;
        if (tryCombination(stat)==i) curkey = 1;
        int l = 0, r = rem.size()-1, ret = rem.size()-1;
        while (l<=r){
            int mid = (l+r)/2;
            for (int j=0; j<=mid; j++) stat[rem[j]] = curkey;
            for (int j=mid+1; j<rem.size(); j++) stat[rem[j]] = 1-curkey;
            if (tryCombination(stat)==i){
                l = mid+1;
            }
            else{
                ret = mid;
                r = mid-1;
            }
        }
        vis[ret] = true;
        stat[ret] = curkey;
        locat[ret] = i;
    }
    answer(stat, locat);
}


#ifdef davele

#endif // davele

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