Submission #645936

#	Time	Username	Problem	Language	Result	Execution time	Memory
645936		ymm	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	7 ms	616 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct tri {
	int l1, r1;
	int l2, r2;
};
int cnt = 1;
vector<pair<int, vector<tri>>> sym = {{0, {{1, 5589, 1, 5589}}}};
const int divvs = 8;
int divv[divvs] = {3, 3, 3, 3, 3, 2, 2, 1};

std::vector<std::vector<int>> devise_strategy(int N) {
	vector<tri> vlst = sym[0].second;
	for (int j = 0;; ++j) {
		//cout << j << ' ' << vlst.size() << '\n';
		if (j >= divvs)
			break;
		int k = divv[j];
		vector<vector<tri>> vec(k);
		vector<tri> nlst;
		for (auto [l1, r1, l2, r2] : vlst) {
			if (j&1) {
				l2 = max(l2, l1+1);
				r2 = min(r2, r1-1);
				if (l2 >= r2)
					continue;
				assert((r2 - l2)%k == 0);
				int len = (r2 - l2) / k;
				for (int p = 0; p < k; ++p) {
					vec[p].push_back({l1, r1, l2 + p*len, l2 + (p+1)*len});
					nlst.push_back({l1, r1, l2 + p*len, l2 + (p+1)*len});
				}
			} else {
				l1 = max(l1, l2+1);
				r1 = min(r1, r2-1);
				if (l1 >= r1)
					continue;
				assert((r1 - l1)%k == 0);
				int len = (r1 - l1) / k;
				for (int p = 0; p < k; ++p) {
					vec[p].push_back({l1 + p*len, l1 + (p+1)*len, l2, r2});
					nlst.push_back({l1 + p*len, l1 + (p+1)*len, l2, r2});
				}
			}
		}
		Loop (p,0,k)
			sym.push_back({j+1, vec[p]});
		vlst = nlst;
	}
	//cout << sym.size() << '\n';
	assert(sym.size() == 21);
	vector<vector<int>> ans(21, vector<int>(N+1));
	Loop (i,0,21) {
		ans[i][0] = i&1;
		Loop (j,1,N+1) {
			if (sym[i].first&1) {
				int p = 0;
				while (p < sym[i].second.size() && j < sym[i].second[p].l2 || sym[i].second[p].r2 <= j)
					++p;
				if (p == sym[i].second.size())
					continue;
				auto [l1, r1, l2, r2] = sym[i].second[p];
				if (j <= l1)
					ans[i][j] = -2;
				else if (r1-1 <= j)
					ans[i][j] = -1;
				else {
					l2 = max(l2, l1+1);
					r2 = min(r2, r1-1);
					int x = (j - l2) / ((r2 - l2) / divv[sym[i].first]);
					int nxt = x+1;
					Loop (z,0,sym[i].first)
						nxt += divv[z];
					ans[i][j] = nxt;
				}
			} else {
				int p = 0;
				while (p < sym[i].second.size() && j < sym[i].second[p].l1 || sym[i].second[p].r1 <= j)
					++p;
				if (p == sym[i].second.size())
					continue;
				auto [l1, r1, l2, r2] = sym[i].second[p];
				if (j <= l2)
					ans[i][j] = -1;
				else if (r2-1 <= j)
					ans[i][j] = -2;
				else {
					l1 = max(l1, l2+1);
					r1 = min(r1, r2-1);
					int x = (j - l1) / ((r1 - l1) / divv[sym[i].first]);
					int nxt = x+1;
					Loop (z,0,sym[i].first)
						nxt += divv[z];
					ans[i][j] = nxt;
				}
			}
		}
	}
	return ans;
	//vector<vector<int>> ans(20, vector<int>(N+1));
	//Loop (i,0,BITS) {
	//	int ii = 1 << (BITS-1-i);
	//	ans[i*3+0].push_back(0);
	//	ans[i*3+1].push_back(1);
	//	ans[i*3+2].push_back(1);
	//	Loop (x,1,N+1) {
	//		ans[i*3+0].push_back(x&ii? i*3 + 2: i*3 + 1);
	//		ans[i*3+1].push_back(x&ii? -1: (i+1)*3);
	//		ans[i*3+2].push_back(x&ii? (i+1)*3: -2);
	//	}
	//}
	//ans[BITS*3].resize(N+1);
	//return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while (p < sym[i].second.size() && j < sym[i].second[p].l2 || sym[i].second[p].r2 <= j)
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:65:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   65 |     while (p < sym[i].second.size() && j < sym[i].second[p].l2 || sym[i].second[p].r2 <= j)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if (p == sym[i].second.size())
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     while (p < sym[i].second.size() && j < sym[i].second[p].l1 || sym[i].second[p].r1 <= j)
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:85:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |     while (p < sym[i].second.size() && j < sym[i].second[p].l1 || sym[i].second[p].r1 <= j)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:87:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if (p == sym[i].second.size())
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~

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