Submission #676966

#	Time	Username	Problem	Language	Result	Execution time	Memory
676966		MilosMilutinovic	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	8 ms	980 KiB

prison

#include "prison.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int K = 30;
int seq[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
int sum[] = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33};
int p[30];
vector<vector<int>> ans;

int get_bit(int x, int k) {
	for (int i = 9; i > k; i--) x /= seq[i];
	return x % seq[k];
}

void build(int l, int r, int x) {
//	printf("SEG %d %d  = %d\n", l, r, x);
	int his_bag = (p[x] % 2 == 1 ? 1 : 2);
	int my_bag = (his_bag ^ 1 ^ 2);
	ans[x][l] = -my_bag;
	ans[x][r] = -his_bag;
	vector<int> pp[seq[p[x]]];
	for (int i = l + 1; i < r; i++)
		pp[get_bit(i, p[x])].push_back(i);
//	printf("wtf!\n");
	for (int i = 1; i <= l; i++) ans[x][i] = -my_bag;
	for (int i = r; i < ans[0].size(); i++) ans[x][i] = -his_bag;
	if (x == 0) {
		for (int k = 0; k < seq[p[x]]; k++) {
			if (pp[k].empty()) continue;
			int L = pp[k][0], R = L;
			for (int j : pp[k]) {
				L = min(L, j);
				R = max(R, j);
				ans[x][j] = k + 1;
			}
			build(L, R, k + 1);
		}
	} else {
		int bit = (x - sum[p[x] - 1]) - 1;
		for (int k = 0; k < bit; k++)
			for (int j : pp[k])
				ans[x][j] = -my_bag;
		for (int k = bit + 1; k < seq[p[x]]; k++)
			for (int j : pp[k])
				ans[x][j] = -his_bag;
		if (!pp[bit].empty()) {
			map<int, vector<int>> go;
			for (int j : pp[bit]) {
				ans[x][j] = sum[p[x]] + get_bit(j, p[x] + 1) + 1;
				go[ans[x][j]].push_back(j);
			}
			for (auto& p : go) {
				int L = p.second[0], R = L;
				for (int j : p.second) {
					L = min(L, j);
					R = max(R, j);
				}
				build(L, R, p.first);
			}
		}
	}
}

vector<vector<int>> devise_strategy(int n) {
	ans.resize(K);
	for (int i = 0; i < K; i++)
		ans[i].resize(n + 1);
	for (int i = 1; i <= K; i++) {
		p[i] = p[i - 1];
		while(sum[p[i]] < i) p[i]++;
	}
	for (int i = 0; i < K; i++)
		ans[i][0] = (p[i] & 1);
	build(1, n, 0);
//	for (int i = 0; i < K; i++) {
//		for (int j = 0; j <= n; j++) {
//			printf("%d ", ans[i][j]);
//		}
//		printf("\n \n");
//	}
	return ans;
}

Compilation message (stderr)

prison.cpp: In function 'void build(int, int, int)':
prison.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = r; i < ans[0].size(); i++) ans[x][i] = -his_bag;
      |                  ~~^~~~~~~~~~~~~~~
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:121:16: warning: iteration 29 invokes undefined behavior [-Waggressive-loop-optimizations]
  121 |   while(sum[p[i]] < i) p[i]++;
      |             ~~~^
prison.cpp:119:20: note: within this loop
  119 |  for (int i = 1; i <= K; i++) {
      |                  ~~^~~~

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