Submission #154351

#	Time	Username	Problem	Language	Result	Execution time	Memory
154351		arnold518	Cave (IOI13_cave)	C++14	0 / 100	811 ms	536 KiB

cave

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5000;

int N, S[MAXN+10], D[MAXN+10], T[MAXN+10];

void exploreCave(int _N)
{
    int i, j;
    N=_N;

    for(i=0; i<N; i++)
    {
        memset(T, 0, sizeof(T));
        for(j=0; j<i; j++) T[D[j]]=S[j];

        int t=tryCombination(T);
        if(t==-1 || t>i) S[i]=0;
        else S[i]=1;

        int lo=-1, hi=N-1;
        while(lo+1<hi)
        {
            int mid=lo+hi>>1;

            for(j=0; j<N; j++)
            {
                if(j<mid) T[j]=!S[i];
                else T[j]=S[i];
            }
            for(j=0; j<i; j++) T[D[j]]=S[j];

            t=tryCombination(T);
            if(t==-1 || t>i) hi=mid;
            else lo=mid;
        }
        D[i]=hi;
    }
    answer(S, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:30:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid=lo+hi>>1;
                     ~~^~~

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