제출 #1310816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310816		dimitri.shengelia	동굴 (IOI13_cave)	C++20	0 / 100	133 ms	556 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

int tryCombination ( int S[] );

void answer( int S[], int D[] );

void exploreCave( int n ) {

	int a[n], b[n];
	fill ( a, a + n, 0 );
	fill ( b, b + n, -1 );

	vector <int> v;

	int k;

	int l, r, z;

	for ( int i = 0; i < n; i++ ) {

		v.push_back( i );

	}

	for ( int i = 0; i < n; i++ ) {

		for ( auto x : v ) {

			a[x] = 0;

		}

		k = tryCombination( a );

		if ( k == -1 or k > i ) {

			a[i] = 0;

			k = 0;

		} else {

			a[i] = 1;

			k = 1;

		}

		l = 0, r = v.size();

		while ( l <= r ) {

			int m = ( l + r ) / 2;

			for ( int j = m + 1; j < (int)v.size(); j++ ) {

				a[v[j]] = 1 - k;

			}

			if ( tryCombination( a ) > i ) {

				r = m - 1;
				
				z = m;

			} else {

				l = m + 1;

			}

		}

		b[v[z]] = i;

		v.erase( v.begin() + z );

	}

	answer( a, b );

	return;

}

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