Submission #744875

#	Time	Username	Problem	Language	Result	Execution time	Memory
744875		jiahng	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1108 KiB

prison

#include "prison.h"

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

typedef long long ll;
//~ #define ll int
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef pair<pi, ll> pii;
typedef set<ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i, s, e) for (int i = s; i <= int(e); ++i)
#define DEC(i, s, e) for (int i = s; i >= int(e); --i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i, x) for (auto i : x)
#define mem(x, i) memset(x, i, sizeof x)
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define maxn 200010
#define INF (ll)1e18
#define MOD 998244353
typedef pair<vi, int> pvi;
typedef pair<int, pi> ipi;
typedef vector<pii> vpii;
#define DEBUG 0
typedef pair <pi,pi> pipi;
typedef vector <pipi> vpipi;
typedef pair <string, int> psi;

int get_bit(int x,int k){
	FOR(i,1,k){
		x /= 3;
	}
	return x % 3;
}

std::vector<std::vector<int>> devise_strategy(int N) {
	vector <vi> ans;

	// a = 0 : last B
	// a = 1 : last A, off
	// a = 2 : last A, on
	
	int idx[20][20];
	
	vpi states;
	states.pb(pi(-1,-1));
	FOR(a,0,2) FOR(k,0,7){
		if (k == 0 && a != 1) continue;
		idx[a][k] = states.size();
		states.pb({a,k});
	}
	//~ cout << states.size() << '\n';
	vi v(N+1);
	v[0] = 0; // query A first
	FOR(i,1,N) v[i] = idx[get_bit(i,7)][7];
	ans.pb(v);
	FOR(i,1,states.size()-1){
		int a = states[i].f, k = states[i].s;
		vi res(N+1,0);
		res[0] = (k % 2 == 1); // B if bit is even, currently a stores A

		FOR(x,1,N){
			if (k % 2 == 1){
				if (get_bit(x,k) != a){
					if (a > get_bit(x,k)) res[x] = -2;
					else res[x] = -1;	
				}else{
					int a2 = get_bit(x,k-1); 
					int k2 = k-1;
					assert(a2 < 3);
					//~ assert(k2 == -1 || idx[a2][k2] != 0);
					
					if (k2 == 0 && a2 != 1){
						if (a2 == 0) res[x] = -2;
						else res[x] = -1;
						continue;
					}
					res[x] = (k2 == -1 ? 0 : idx[a2][k2]);
				}
			}else{
				if (get_bit(x,k) != a){
					if (a > get_bit(x,k)) res[x] = -1;
					else res[x] = -2;
				}else{
					int a2 = get_bit(x,k-1);
					int k2 = k-1;
					assert(a2 < 3);
					//~ assert(k2 == -1 || idx[a2][k2] != 0);
					if (k2 == 0 && a2 != 1){
						if (a2 == 0) res[x] = -1;
						else res[x] = -2;
						continue;
					}
					res[x] = (k2 == -1 ? 0 : idx[a2][k2]);
				}
			}
		}
		//~ aFOR(j, res) assert(j <= 26);
		//~ aFOR(j,res) cout << j << ' ';
		//~ cout << '\n';
		ans.pb(res);
	}
	//~ cout << ans.size() << '\n';
	return ans;

}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 70 / 90