Submission #657868

#	Time	Username	Problem	Language	Result	Execution time	Memory
657868		gg123_pe	Cave (IOI13_cave)	C++14	0 / 100	121 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; 

/*
vector <int> s, d, p; 
int n; 

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

void answer(vector <int> si, vector <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;  
		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"; 
            */
			if(tri(v) != val) r = m; 
			else l = m+1; 

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

    
			if(tri(v) <= val) 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; 

	s.resize(n), d.resize(n), p.resize(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