Submission #670761

#	Time	Username	Problem	Language	Result	Execution time	Memory
670761		sofija6	Cave (IOI13_cave)	C++14	100 / 100	725 ms	464 KiB

cave

#include <bits/stdc++.h>
#define ll int
#include "cave.h"
using namespace std;
void exploreCave(int N)
{
    ll a[N],S[N],D[N];
    bool f[N];
    for (ll i=0;i<N;i++)
    {
        a[i]=1;
        f[i]=false;
    }
    for (ll i=0;i<N;i++)
    {
        if (tryCombination(a)!=i)
        {
            for (ll j=0;j<N;j++)
            {
                if (!f[j])
                    a[j]=1-a[j];
            }
        }
        ll l=1,r=N-i,mid,cnt,ans,last;
        while (l<=r)
        {
            mid=(l+r)/2;
            cnt=mid;
            for (ll j=0;j<N;j++)
            {
                if (!cnt)
                    break;
                if (!f[j])
                {
                    a[j]=1-a[j];
                    cnt--;
                    last=j;
                }
            }
            if (tryCombination(a)==i)
                l=mid+1;
            else
            {
                r=mid-1;
                ans=last;
            }
            cnt=mid;
            for (ll j=0;j<N;j++)
            {
                if (!cnt)
                    break;
                if (!f[j])
                {
                    a[j]=1-a[j];
                    cnt--;
                }
            }
        }
        S[ans]=1-a[ans];
        a[ans]=1-a[ans];
        f[ans]=true;
        D[ans]=i;
    }
    answer(S,D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:62:15: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |         D[ans]=i;
      |         ~~~~~~^~

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