Submission #1077119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077119		allin27x	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	348 KiB

prison

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


std::vector<std::vector<int>> devise_strategy(int N){
	vector ans(22, vector (N+1, 0));
	vector<vector<pair<int,int>>> rgs(27);
	rgs[0].push_back(make_pair(1,5000));
	vector<pair<int,int>> curr; curr.push_back(make_pair(1,5000));
	vector<pair<int,int>> nc;
	for (int i=0; i<7; i++) {
		for (auto [l,r]: curr) {
			l++; r--;
			rgs[3*i+1].push_back({l, (2*l+r)/3});
			nc.push_back({l, (2*l+r)/3});
		}
		for (auto [l,r]: curr) {
			l++; r--;
			rgs[3*i+2].push_back({(2*l+r)/3 + 1, (l+2*r)/3});
			nc.push_back({(2*l+r)/3 + 1, (l+2*r)/3});
		}
		for (auto [l,r]: curr) {
			l++; r--;
			rgs[3*i+3].push_back({(l+2*r)/3+1, r});
			nc.push_back({(l+2*r)/3+1, r});
		}
		curr = nc; nc.clear();
	}

	ans[0][0] = 0; ans[0][1] = -1; ans[0][N] = -2;
	for (int i=2; i<N; i++) {
		for (auto [l,r]: rgs[1]) {
			if (l<i && i<r) ans[0][i] = 1;
			if (i==l) ans[0][i] = -1;
			if (i==r) ans[1][l] = -2;
		}
		for (auto [l,r]: rgs[3]) {
			if (l<=i && i<=r) ans[0][i] = 3;
			if (i==l) ans[0][i] = -1;
			if (i==r) ans[1][l] = -2;
		}
		for (auto [l,r]: rgs[2]) {
			if (l<=i && i<=r) ans[0][i] = 2;
			if (i==l) ans[0][i] = -1;
			if (i==r) ans[1][l] = -2;
		}
	}
	for (int i=1; i<22; i++) {
		int pl = (i-1)/3 % 2;
		int bl = (i-1)/3; int first_pr = (i-1) % 3;
		ans[i][0] = !pl;
		int ll = rgs[bl*3 + 1][0].first; int rr = rgs[bl*3+3].back().second;
		for (int j=1; j<=N; j++) {
			int sec_pr = -1;
			int on_lf =0, on_rg =0;
			for (auto [l,r]: rgs[bl*3 + 1]) {
				if (l<=j && j<=r) {
					sec_pr = 0;
				}
				if (l==j) on_lf = 1; if (j==r) on_rg = 1;
			}
			for (auto [l,r]: rgs[bl*3 + 2]) {
				if (l<=j && j<=r) {
					sec_pr = 1;
				}
				if (l==j) on_lf = 1; if (j==r) on_rg = 1;

			}
			for (auto [l,r]: rgs[bl*3 + 3]) {
				if (l<=j && j<=r) {
					sec_pr = 2;
				}
				if (l==j) on_lf = 1; if (j==r) on_rg = 1;
			}
			int new_sc;
			for (auto [l,r]: rgs[bl*3 + 4]) {if (l<=j && j<=r) new_sc = 0; if (l==j)on_lf=1; if (j==r) on_rg = 1;}
			for (auto [l,r]: rgs[bl*3 + 5]) {if (l<=j && j<=r) new_sc = 1; if (l==j)on_lf=1; if (j==r) on_rg = 1;}
			for (auto [l,r]: rgs[bl*3 + 6]) {if (l<=j && j<=r) new_sc = 2; if (l==j)on_lf=1; if (j==r) on_rg = 1;}
			if (sec_pr == -1) {
				if (j <= ll) ans[i][j] = -1 -!pl;
				if (j >= rr) ans[i][j] = -1 - pl;
			} else {
				if (first_pr == sec_pr) {
					ans[i][j] = bl*3 + 4 + new_sc;
					if (ans[i][j] >= 22) ans[i][j] = -1;
					if (on_lf) ans[i][j] = -1-!pl;
					if (on_rg) ans[i][j] = -1 - pl;
				}
				if (first_pr < sec_pr) ans[i][j] = -1 -pl;
				if (first_pr > sec_pr) ans[i][j] = -1 - !pl;
			}
		}
	}

	return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:60:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   60 |     if (l==j) on_lf = 1; if (j==r) on_rg = 1;
      |     ^~
prison.cpp:60:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   60 |     if (l==j) on_lf = 1; if (j==r) on_rg = 1;
      |                          ^~
prison.cpp:66:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   66 |     if (l==j) on_lf = 1; if (j==r) on_rg = 1;
      |     ^~
prison.cpp:66:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   66 |     if (l==j) on_lf = 1; if (j==r) on_rg = 1;
      |                          ^~
prison.cpp:73:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   73 |     if (l==j) on_lf = 1; if (j==r) on_rg = 1;
      |     ^~
prison.cpp:73:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   73 |     if (l==j) on_lf = 1; if (j==r) on_rg = 1;
      |                          ^~
prison.cpp:84:27: warning: 'new_sc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |      ans[i][j] = bl*3 + 4 + new_sc;
      |                  ~~~~~~~~~^~~~~~~~

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