Submission #774170

#	Time	Username	Problem	Language	Result	Execution time	Memory
774170		Trumling	Cave (IOI13_cave)	C++14	13 / 100	172 ms	400 KiB

cave

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

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
//tryCombination
/*
#include <stdio.h>
#include <stdlib.h>
#include "cave.h"
 
#define MAX_N 5000
#define MAX_CALLS 70000

#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)


#define N koala
#define realS kangaroo
#define realD possum
#define inv platypus
#define num_calls echidna

 int N;
 int realS[MAX_N];
 int realD[MAX_N];
 int inv[MAX_N];
 int num_calls;

void answer(int S[], int D[]) {
    int i;
    int correct = 1;
    for (i = 0; i < N; ++i)
        if (S[i] != realS[i] || D[i] != realD[i]) {
            correct = 0;
            break;
        }

    if (correct)
        printf("CORRECT\n");
    else
        printf("INCORRECT\n");

    for (i = 0; i < N; ++i) {
        if (i > 0)
            printf(" ");
        printf("%d", S[i]);
    }
    printf("\n");

    for (i = 0; i < N; ++i) {
        if (i > 0)
            printf(" ");
        printf("%d", D[i]);
    }
    printf("\n");

    exit(0);
}

int tryCombination(int S[]) {
    int i;

    if (num_calls >= MAX_CALLS) {
        printf("INCORRECT\nToo many calls to tryCombination().\n");
        exit(0);
    }
    ++num_calls;

    for (i = 0; i < N; ++i)
        if (S[inv[i]] != realS[inv[i]])
            return i;
    return -1;
}

int init() {
    int i, res;

    FILE *f = fopen("cave.in", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d", &N);

    for (i = 0; i < N; ++i) {
        res = fscanf(f, "%d", &realS[i]);
    }
    for (i = 0; i < N; ++i) {
        res = fscanf(f, "%d", &realD[i]);
        inv[realD[i]] = i;
    }

    num_calls = 0;
    return N;
}
*/
void exploreCave(int N) 
{
int s[N]={ },d[N];
ll i=tryCombination(s);
bool no[N]={ };
while(i!=-1)
{
for(int j=0;j<N;j++)
{
    if(no[j])
    continue;

    s[j]=s[j]^1;
    int pos=tryCombination(s);
    

    if(pos>i || pos==-1)
    {
        d[j]=i;
        i=pos;
        no[j]=1;
        
    }
    else
    {
    s[j]=s[j]^1;
    if(pos<i )
    {
        no[j]=1;
        d[j]=pos;
    }
    }
}
}

for(int j=0;j<N;j++)
{
    if(no[j])
    continue;
    s[j]=s[j]^1;
    int pos=tryCombination(s);
    s[j]=s[j]^1;
    d[j]=pos;
}

answer(s,d);
}

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