Submission #730032

#	Time	Username	Problem	Language	Result	Execution time	Memory
730032		DeMen100ns	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1064 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
int bel[5010];
vector<vector<int>> devise_strategy(int n) {
	vector<vector<int> > res(21,vector<int>(n+1));
	for (int I=0;I<8;I++) {
		int L=0,R=0;
		if (I) L=(I-1)*3+1,R=L+2;
		R=min(R,20);
		for (int i=L;i<=R;i++) res[i][0]=I&1;
		int A=-1,B=-2; if (I&1) swap(A,B);
		for (int i=L;i<=R;i++) {
			vector<int> vec;
			for (int j=1;j<=n;j++) {
				if (bel[j]<i) res[i][j]=A;
				else if (bel[j]>i) res[i][j]=B;
				else {
					vec.push_back(j);
				}
			}
			vector<pair<int,int> > V;
			for (int j=0;j<vec.size();j++) {
				if ((int)V.size()&&V.back().second==vec[j]-1) V.back().second++;
				else V.push_back(MP(vec[j],vec[j]));
			}
			for (pair<int,int> &AA : V) {
				int l=AA.first,r=AA.second;
				res[i][l]=A,res[i][r]=B;
				int p=R,len=(r-1-l+2)/3;
				if (I==7) len=(r-1-l+1)/2;
			//	printf("%d %d %d\n",l,r,len);
				for (int k=l+1;k<r;k++) {
					if ((k-l-1)%len==0) p++;
					res[i][k]=min(p,20);
				}
			}
		}
		for (int i=1;i<=n;i++) if (bel[i]>=L&&bel[i]<=R) { bel[i]=res[bel[i]][i]; if (bel[i]==B) bel[i]=1e9; }
		//for (int i=1;i<=n;i++) printf("%d ",bel[i]); puts("");
	}
	return res;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    for (int j=0;j<vec.size();j++) {
      |                 ~^~~~~~~~~~~

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