Submission #60880

#	Time	Username	Problem	Language	Result	Execution time	Memory
60880		updown1	Cave (IOI13_cave)	C++17	0 / 100	2085 ms	512 KiB

cave

/*
Brute force w/ random to eliminate worse case scenarios
*/
//#include "grader.h"
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, P)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations

void exploreCave(int N) {
    srand (time(NULL));
    int S[N], D[N];
    bool done[N], dd1[N];
    ffi S[i] = 0, done[i] = dd1[i] = false;
    int farprev = tryCombination(S);
    if (farprev == -1) farprev = N+1;
    int diff = 0;
    S[0] = 1;
    dd1[0] = true;
    int far = tryCombination(S);
    if (far == -1) far = N+1;
    bool good = false;
    while (!good) {
        //w << diff c far s farprev<<e;
        /// React to the difference
        if (far < farprev) {S[diff] = 1-S[diff]; done[diff] = true; D[diff] = far; ffi dd1[i] = false;}
        else if (far > farprev) {done[diff] = true; D[diff] = farprev; ffi dd1[i] = false;}
        //ffi w<< done[i]<< " "; w<<e;
        //ffi w<< dd1[i] << " "; w<<e;
        good = true;
        ffi if (!done[i]) good = false;
        if (good) break;
        while (dd1[diff] || done[diff]) {
            diff += rand();
            diff %= N;
            //w<< diff<<e;
        }
        dd1[diff] = true;
        S[diff] = 1-S[diff];
        farprev = far;
        far = tryCombination(S);
        if (far == -1) far = N+1;
    }
    //w<< "DADASD"<<e;
    answer(S, D);
}

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