Submission #210768

#	Time	Username	Problem	Language	Result	Execution time	Memory
210768		Nucleist	Cave (IOI13_cave)	C++14	100 / 100	1306 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
vector<int>S,D;
bool vis[5001];
void exploreCave(int N)
{
	int S[N]={0};
	int D[N]={0};
	int cur=0;
	int next=0;
	int trial[N]={0};
	int k = tryCombination(trial);
	if(k==0)cur=1;
	for (int i = 0; i < N; ++i)
	{
		int low=0;
		int high=N-1;
		for (int j = 0; j < N; ++j)
		{
			if(!vis[j])trial[j]=cur;
		}
		int yo=tryCombination(trial);
		//debugs(yo,i);
		if(yo>i+1 || yo==-1)next=cur;
		else next=1-cur;
		int ans=0;
		while(low<=high)
		{
			int med=(low+high)/2;
			for (int j = 0; j <= med; ++j)
			{
				if(!vis[j])trial[j]=cur;
			}
			for (int j = med+1; j < N; ++j)
			{
				if(!vis[j])trial[j]=1-cur;
			}
			int ko=tryCombination(trial);
			if(ko>i || ko==-1)
			{
				high=med;
				ans=med;
				if(high==low)break;
			}
			else
			{
				low=med+1;
				ans=med+1;
			}
		}
		S[ans]=cur;
		D[ans]=i;
		vis[ans]=1;
		cur=next;
	}
	answer(S,D);
}
//

Compilation message (stderr)

cave.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
cave.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

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