Submission #281726

#	Time	Username	Problem	Language	Result	Execution time	Memory
281726		Kastanda	Cave (IOI13_cave)	C++11	100 / 100	348 ms	760 KiB

cave

// M
#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
const int N = 5005;
int C[N], M[N];

void exploreCave(int n)
{
        memset(M, -1, sizeof(M));
        for (int i = 0; i < n; i ++)
        {
                int rs = tryCombination(C);
                if (rs == -1)
                        rs = n;
                assert(rs >= i);
                int w = (rs == i);
                vector < int > vec;
                for (int j = 0; j < n; j ++)
                        if (M[j] == -1)
                                vec.push_back(j);
                int le = 0, ri = (int)vec.size(), md;
                while (ri - le > 1)
                {
                        md = (le + ri) >> 1;
                        for (int j = md; j < ri; j ++)
                                C[vec[j]] ^= 1;
                        int w2 = tryCombination(C) == i;
                        if (w2 == w)
                                ri = md;
                        else
                                le = md;
                        for (int j = md; j < ri; j ++)
                                C[vec[j]] ^= 1;
                }
                M[vec[le]] = i;
                if (w == 1)
                        C[vec[le]] ^= 1;
        }
        answer(C, M);
        return ;
}

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