Submission #1081581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081581		MMihalev	Cave (IOI13_cave)	C++14	100 / 100	463 ms	824 KiB

cave

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include "cave.h"
using namespace std;
const int MAX_N=5e3+5;
int lights[MAX_N];
int used[MAX_N];
int s[MAX_N];
int d[MAX_N];
void flip(int x)
{
    for(int i=0;i<=x;i++)
    {
        if(used[i])continue;
        lights[i]=1-lights[i];
    }
}
void exploreCave(int N)
{
    for(int it=0;it<N;it++)
    {
        int door=tryCombination(lights);
        int closed=(door==it ? 1 : 0);
        int postochange;

        int l=0,r=N-1;
        int pos;
        while(l<=r)
        {
            int mid=(l+r)/2;
            flip(mid);
            int doornow=tryCombination(lights);

            if((closed && doornow!=it) or (!closed && doornow==it))
            {
                pos=mid;
                postochange=lights[pos];
                r=mid-1;
            }
            else l=mid+1;

            flip(mid);
        }
        d[pos]=it;
        used[pos]=1;
        if(closed)s[pos]=postochange;
        else s[pos]=1-postochange;
        lights[pos]=s[pos];
    }
    answer(s,d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:50:20: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |         lights[pos]=s[pos];
      |         ~~~~~~~~~~~^~~~~~~
cave.cpp:49:22: warning: 'postochange' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |         else s[pos]=1-postochange;
      |                     ~^~~~~~~~~~~~

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