Submission #426709

#	Time	Username	Problem	Language	Result	Execution time	Memory
426709		arayi	Cave (IOI13_cave)	C++17	0 / 100	448 ms	552 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);
}

Compilation message (stderr)

cave.cpp: In function 'void slv(int)':
cave.cpp:15:24: warning: array subscript -1 is below array bounds of 'int [5050]' [-Warray-bounds]
   15 |         else s[d[i] - 1] = 0;
      |              ~~~~~~~~~~^
cave.cpp:8:11: note: while referencing 's'
    8 | int d[N], s[N], a[N];
      |           ^

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