Submission #426746

#	Time	Username	Problem	Language	Result	Execution time	Memory
426746		arayi	Cave (IOI13_cave)	C++17	100 / 100	1148 ms	572 KiB

cave

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

const int N = 5050;
int n;
int d[N], s[N], a[N];
int col[N];
void slv(int i1)
{
    for (int i = 1; i < i1; i++)
    {
        if(d[i] > 0) s[d[i] - 1] = 1;
        else s[-d[i] - 1] = 0;
    }
    vector<int> fp;
    for (int i = 1; i <= n; i++)
        if(!col[i]) fp.ad(i), s[i - 1] = 0;
    int sm = tryCombination(s) + 1;
    if(sm == 0) sm = n + 1;
    int l = 0, r = fp.size() - 1, ans = fp.size() - 1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = 1; i <= n; i++) if(!col[i]) s[i - 1] = 0;
        for (int i = l; i <= mid; i++) s[fp[i] - 1] = 1;
        int ss = tryCombination(s) + 1;
        if(ss == 0) ss = n + 1;
        if((sm == i1 && ss > i1) || (ss == i1 && sm > i1)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    col[fp[ans]] = 1;
    if(sm > i1) d[i1] = -fp[ans];
    else d[i1] = fp[ans];
}
void exploreCave(int N) 
{
    n = N;
    for (int i = 1; i <= n; i++)
        slv(i);
    for (int i = 1; i <= n; i++)
    {
        d[i-1] = abs(d[i]) - 1;
        a[d[i-1]] = i - 1;
        if(d[i] > 0) s[d[i - 1]] = 1;
        else s[d[i - 1]] = 0;
    }
    answer(s, a);
}

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