Submission #105106

#	Time	Username	Problem	Language	Result	Execution time	Memory
105106		mrtsima22	Cave (IOI13_cave)	C++17	100 / 100	1119 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
 #define LSOne(S) (S & (-S))
#define ll long long
#define pii pair<int,int>
#define twol pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define mk make_pair
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
#define MAXN 5005
using namespace std;
int N ;
int A[MAXN] , B[MAXN] , s[MAXN];
int resp1[MAXN] , resp2[MAXN] ;
pii ans[MAXN] ;
int findDoor( int door ){
	memset(s , 0 , sizeof s) ;
	for(int i=0;i<N;i++) if( A[i] != -1 ) s[ A[i] ] = B[i] ;
	int k = tryCombination(s) ;
	if(k == -1) k = door + 1 ;
	if( k > door ) return B[door] = 0 ;
	else return B[door] = 1 ;
}
int findSwitch( int door ){
	int u = 0 , l = N-1 , mid ,x = B[door] ;
	while( u < l ){
		mid = (u+l)/2 ;
		memset(s , -1 , sizeof s) ;
		for(int i=0;i<N;i++) if(A[i] != -1) s[ A[i] ] = B[ i ] ;
		for(int i=u;i<=mid;i++) if(s[i] == -1 ) s[i] = x ;
		for(int i=mid;i<=l;i++) if( s[i] == -1 ) s[i] = x^1 ;
		int k = tryCombination(s) ;
		if( k == -1 ) k = door + 1 ;
		if(k > door) l = mid ;
		else u = mid + 1 ;
	}
	return l  ;
}
 
void exploreCave( int n ){
	N=n;
	memset(A, -1 , sizeof A) ;memset(B, -1, sizeof B) ;
	for(int i=0;i<N;i++) B[i] = findDoor(i) ,A[i] = findSwitch(i) ;
	pii p[MAXN] ;
	for(int i=0;i<N;i++) p[i] = pii( A[i] , i ) ;
	sort(p,p+N) ;
	for(int i=0;i<N;i++) resp1[i] = p[i].ss ;
	for(int i=0;i<N;i++) resp2[i] = B[ p[i].ss ] ;
	answer(resp2, resp1) ;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/

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