Submission #539166

#	Time	Username	Problem	Language	Result	Execution time	Memory
539166		astoria	Cave (IOI13_cave)	C++14	100 / 100	874 ms	468 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int finalval[5005];

int f(int m){
    int s[n];
    int counter=0;
    int secct=0;
    for (int i=0; i<n; i++){
        if (finalval[i] != -1){
            s[i] = finalval[i];
            secct++;
        } 
        else{
            if (counter < m){
                counter++;
                s[i] = 0;
            }
            else {
                s[i] = 1;
            }
        }
    }
    int x = tryCombination(s);
    if (x>secct || x==-1) return 1;
    else return 0;
}

int g(int m){
    int s[n];
    int counter=0;
    int secct=0;
    for (int i=0; i<n; i++){
        if (finalval[i] != -1){
            s[i] = finalval[i];
            secct++;
        } 
        else{
            if (counter < m){
                counter++;
                s[i] = 1;
            }
            else {
                s[i] = 0;
            }
        }
    }
    int x = tryCombination(s);
    if (x>secct || x==-1) return 1;
    else return 0;
}

int bs0(int ct){
    int l=1, r=n-ct;
    while (l<r){
        int m=(l+r)/2;
        if (f(m)) r=m;
        else l=m+1;
    }
    int pos;
    int coolcounter=0;
    for (int i=0; i<n; i++){
        if (finalval[i] == -1) coolcounter++;
        if (coolcounter == l){
            pos = i;
            break;
        }
    }
    return pos;
}

int bs1(int ct){
    int l=1, r=n-ct;
    while (l<r){
        int m=(l+r)/2;
        if (g(m)) r=m;
        else l=m+1;
    }
    int pos;
    int coolcounter=0;
    for (int i=0; i<n; i++){
        if (finalval[i] == -1) coolcounter++;
        if (coolcounter == l){
            pos = i;
            break;
        }
    }
    return pos;
}

void exploreCave(int N) {
    n = N;
    //cout << n;
    
    memset(finalval, -1, sizeof(finalval));
    int D[N]; memset(D, -1, sizeof(D));
    for (int c=0; c<N; c++){
        int S[N];
        for (int j=0; j<N; j++){
            if (finalval[j] != -1) S[j] = finalval[j];
            else S[j] = 0;
        }
        int x = tryCombination(S);
        int ele;
        if (x>c || x==-1) ele = bs0(c);
        else ele = bs1(c);
        D[ele] = c;
        if (x>c || x==-1) finalval[ele] = 0;
        else finalval[ele] = 1;
        //cout << ele << "\n";
    }
    answer(finalval, D);
}

Compilation message (stderr)

cave.cpp: In function 'int bs0(int)':
cave.cpp:72:12: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     return pos;
      |            ^~~
cave.cpp: In function 'int bs1(int)':
cave.cpp:91:12: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |     return pos;
      |            ^~~

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