Submission #1216732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216732		LM1	Cave (IOI13_cave)	C++20	100 / 100	286 ms	520 KiB

cave

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include "cave.h"
 
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
 
#define MAX_N 5000
#define MAX_CALLS 70000
 
#define fail(s, ...) do { \
    fprintf(stderr, s "\n", ##__VA_ARGS__); \
    exit(1); \
} while(0)
 
/* Symbol obfuscation */
#define N koala
#define realS kangaroo
#define realD possum
#define inv platypus
#define num_calls echidna
 
static int N;
static int realS[MAX_N];
static int realD[MAX_N];
static int inv[MAX_N];
static int num_calls;
 
//void answer(int S[], int D[]) {
//    bool correct = true;
//    for (int i = 0; i < N; ++i) {
//        if (S[i] != realS[i] || D[i] != realD[i]) {
//            correct = false;
//            break;
//        }
//    }
// 
//    if (correct)
//        cout << "CORRECT" << endl;
//    else
//        cout << "INCORRECT" << endl;
// 
//    for (int i = 0; i < N; ++i) {
//        if (i > 0) cout << " ";
//        cout << S[i];
//    }
//    cout << endl;
// 
//    for (int i = 0; i < N; ++i) {
//        if (i > 0) cout << " ";
//        cout << D[i];
//    }
//    cout << endl;
// 
//    exit(0);
//}
// 
//int tryCombination(int S[]) {
//    if (num_calls >= MAX_CALLS) {
//        cout << "INCORRECT\nToo many calls to tryCombination()." << endl;
//        exit(0);
//    }
//    ++num_calls;
// 
//    for (int i = 0; i < N; ++i) {
//        if (S[inv[i]] != realS[inv[i]])
//            return i;
//    }
//    return -1;
//}
// 
//int init() {
//    ifstream fin("cave.in");
//    if (!fin)
//        fail("Failed to open input file.");
// 
//    fin >> N;
// 
//    for (int i = 0; i < N; ++i)
//        fin >> realS[i];
// 
//    for (int i = 0; i < N; ++i) {
//        fin >> realD[i];
//        inv[realD[i]] = i;
//    }
// 
//    num_calls = 0;
//    return N;
//}
 
void exploreCave(int N){
	int s[N],d[N];
	bool f[N];
	fr(i,0,N){
		s[i]=0;
		d[i]=0;
		f[i]=0;
	}
	fr(tt,0,N){
		fr(i,0,N){
			if(f[i]==0){
				s[i]=0;
			}
		}
		int x=tryCombination(s);
		int ss;
		if(x!=tt)ss=0;
		else ss=1;
		fr(i,0,N){
			if(f[i]==0){
				s[i]=1-ss;
			}
		}
		int l=0,r=N-1,m,ind=0;
		while(l<r){
			m=(l+r)/2;
			fr(i,l,m+1){
				if(f[i]==0){
					s[i]=ss;
				}
			}
			x=tryCombination(s);
			if(x!=tt){
				ind=m;
				r=m;
			}
			else{
				ind=m+1;
				l=m+1;
			}
			fr(i,l,m+1){
				if(f[i]==0){
					s[i]=1-ss;
				}
			}
		}
		//cout<<ind;
		d[ind]=tt;
		f[ind]=1;
		s[ind]=ss;
	}
	answer(s,d);
}
//int main() {
//    int N;
//    N = init();
//    exploreCave(N);
//    //printf("INCORRECT\nYour solution did not call answer().\n");
//    return 0;
//}
/*
l=0
r=2
m=1


*/

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