Submission #1166185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166185		sano	Cave (IOI13_cave)	C++20	100 / 100	104 ms	568 KiB

cave

#include "cave.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

int n;
int s[5000];

int zisti(vec<int>&nevieme, int hladame, int pos) {
	int l = 0, r = nevieme.size() - 1;
	For(i, nevieme.size()) s[nevieme[i]] = 1 - hladame;
	while (l < r) {
		int mid = (l + r) / 2;
		ffor(i, l, mid + 1) s[nevieme[i]] = hladame;
		int x = tryCombination(s);
		if (x == -1) x = n - 1;
		ffor(i, l, mid + 1) s[nevieme[i]] = 1 - hladame;
		if (x > pos) r = mid;
		else l = mid + 1;
	}
	return l;
}

void exploreCave(int n1) {
	n = n1;
	int d[5000];
	vec<int> nevieme;
	For(i, n) nevieme.push_back(i);
	For(i, n){
		for (auto i : nevieme) s[i] = 0;
		int x = tryCombination(s);
		if (x == -1) {
			x = n + 1;
		}
		int hladame = 1;
		if (x > i) hladame = 0;
		int odp = zisti(nevieme, hladame, i);
		s[nevieme[odp]] = hladame;
		d[nevieme[odp]] = i;
		swap(nevieme[odp], nevieme.back());
		nevieme.pop_back();
	}
	answer(s, d);
	return;
}

/*
signed main() {
	ll t;
	//cin >> t;
	t = 1;
	For(w, t) {
		int n; cin >> n;
		exploreCave(n);
	}
	return 0;
}*/

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