Submission #657895

#	Time	Username	Problem	Language	Result	Execution time	Memory
657895		gg123_pe	Cave (IOI13_cave)	C++14	0 / 100	456 ms	444 KiB

cave

#include "cave.h"
#include <bits/stdc++.h> 
using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 5005; 

/*
int s[N], d[N], p[N]; 
int n; 

int tryCombination(int v[]){
	f(i,0,n) if(v[p[i]] != s[p[i]]) return i; 
	return -1; 
}

void answer(int si[], int di[]){
	f(i,0,n){
		if(si[i] != s[i] or di[i] != d[i]){
			cout << "WA\n"; 
			return; 
		}
	}
	cout << "AC\n"; 
}
*/


int v[N], S[N], D[N], inv[N]; 
int n; 

void change(int l, int r){
	f(i,l,r+1) if(D[i] == -1) v[i] = 1 - v[i]; 
}

int tri(int r[]){
    int ans = tryCombination(r); 
    if(ans == -1) ans = n; 
    return ans; 
}
void find(int x){
	f(i,0,n) v[i] = 0; 
	f(i,0,x) v[inv[i]] = S[inv[i]]; 

	int l = 0, r = n-1; 
	int val = tri(v); 

	int u; 
	if(val == x) u = 1; 
	else u = 0; 

	while(l < r){
		int m = (l+r)>>1; 
		change(0, m); 

           /*
            cout << l << " " << r << "\n"; 
            f(i,0,n) cout << v[i] << " ";
            cout << "\n" << tryCombination(v) << "\n"; 
            */
        int wi = tri(v); 
		if((wi > x and wi != n) or (wi == n and u == 1)) r = m; 
		else l = m+1; 

		change(0, m); 
	}
	S[l] = u, D[l] = x, inv[x] = l;
}
void exploreCave(int ni) {
	n = ni; 
	f(i,0,n) S[i] = D[i] = inv[i] = -1; 

	f(i,0,n)
		find(i); 
	
    answer(S, D); 
}

/*
int main(){
	cin >> n; 
	
	f(i,0,n) cin >> s[i]; 
	f(i,0,n) cin >> d[i], p[d[i]] = i; 


	exploreCave(n); 
	return 0; 
}
*/

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