Submission #774231

#	Time	Username	Problem	Language	Result	Execution time	Memory
774231		Trumling	Cave (IOI13_cave)	C++14	63 / 100	2013 ms	416 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()

/*
#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;
}
*/
///********************************************************************************************************
//tryCombination
void exploreCave(int n) 
{
int s[n]={ },d[n];
bool no[n]={ };

for(int i=0;i<n;i++)
{
        ll ans1=tryCombination(s),ans;
        if(ans1==-1)
        ans1=INF;
        ll pos=0;
        
        for(int j=0;(1<<j)<n;j++)
        {
            for(int c=0;c<n;c++)
                if(!no[c]  && (c&(1<<j)))
                    s[c]=1;
            ans=tryCombination(s);
            if(ans==-1)
            ans=INF;

            
            if(ans1>i  &&  ans==i)
                pos+=(1<<j);
            if(ans1==i  &&  ans>i)
                pos+=(1<<j);

            for(int c=0;c<n;c++)
                if(!no[c]  && (c&(1<<j)))
                    s[c]=0;
        }
        
        d[pos]=i;
        s[pos]=((ans1>i)?0:1);
        no[pos]=1;
}

answer(s,d);
}

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