제출 #1290504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290504		ghammazhassan	동굴 (IOI13_cave)	C++20	100 / 100	106 ms	584 KiB

cave

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include "cave.h"

using namespace std;
#define MAX_N 5000
#define MAX_CALLS 70000

#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		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[]);
int tryCombination(int S[]);
void exploreCave(int n){
    int a[n];
    int od[n];
    for (int i=0;i<n;i++){
        a[i]=0;
    }
    vector<int>p;
    for (int i=0;i<n;i++){
        p.push_back(i);
    }
    vector<int>an(n);
    int u=0;
    while (u<n){
        int l=0;
        int h=p.size()-1;
        int m=(l+h)/2;
        int x=tryCombination(a);
        if (x==-1 or x>u){
            for (int i:p){
                a[i]^=1;
            }
        }
        while (l<h){
            int d[n];
            for (int i=0;i<n;i++){
                d[i]=a[i];
            }
            for (int i=l;i<=m;i++){
                d[p[i]]^=1;
            }
            int x=tryCombination(d);
            if (x==-1 or x>u){
                h=m;
            }
            else{
                l=m+1;
            }
            m=(l+h)/2;
        }
        a[p[m]]^=1;
        od[p[m]]=u;
        p.erase(p.begin()+m);
        u++;
    }
    answer(a,od);
    // for (int i=0;i<n;i++){
    //     cout << od[i] << " ";
    // }
    // cout << endl;
}
// int main() {
//     #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
//     #endif
//     int i, res;

//     FILE *f = fopen("input.txt", "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;
//     exploreCave(N);
//     cout << N << endl;
// }

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