Submission #991085

#	Time	Username	Problem	Language	Result	Execution time	Memory
991085		RaduM	Cave (IOI13_cave)	C++17	100 / 100	208 ms	604 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;
int v[5005];
int v2[5005];
int p[5005];
void cb(int n, int x, bool opened){
    int st = 0, dr = n - 1, med, poz;
    while(st <= dr){
        med = (st + dr) >> 1;
        for(int i = st; i <= med; i++) if(p[i] == -1) v2[i] ^= 1;
        int t = tryCombination(v2);
        if(t > x || t == -1){
            if(!opened){
                for(int i = st; i <= med; i++) if(p[i] == -1) v2[i] ^= 1;
                dr = med - 1;
                poz = med;
            }
            else st = med + 1;
        }
        else{
            if(!opened){
                st = med + 1;
            }
            else{
                for(int i = st; i <= med; i++) if(p[i] == -1) v2[i] ^= 1;
                dr = med - 1;
                poz = med;
            }
        }
    }
    for(int i = 0; i < n; i++) if(p[i] == -1) v2[i] = 0;
    p[poz] = x;
    if(!opened) v2[poz] ^= 1;
}
void exploreCave(int n){
    memset(v, 0, sizeof v);
    memset(v2, 0, sizeof v2);
    for(int i = 0; i < n; i++) p[i] = -1;
    for(int i = 0; i < n; i++){
        bool opened = 0;
        int t = tryCombination(v2);
        if(t > i || t == -1) opened = 1;
        cb(n, i, opened);
    }
    answer(v2, p);
}
//
//int main()
//{
//    exploreCave(init());
//}

Compilation message (stderr)

cave.cpp: In function 'void cb(int, int, bool)':
cave.cpp:35:25: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |     if(!opened) v2[poz] ^= 1;
      |                 ~~~~~~~~^~~~

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