제출 #1191599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191599		Faisal_Saqib	죄수들의 도전 (IOI22_prison)	C++17	80 / 100	7 ms	1348 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define all(x) begin(x),end(x)
int dp[20][20],c=0,pw[100];
pair<int,int> pt[100];
int findbitvalue(int num,int bit)
{
	return (num/pw[bit])%3;
}
std::vector<std::vector<int>> devise_strategy(int N)
{
	pw[0]=1;
	for(int i=1;i<=10;i++)
		pw[i]=pw[i-1]*3;
	// cout<<0<<" represent bit: "<<13<<" val "<<0<<endl;
	// 7 in A
	// 6 in B
	// 0 in B
	for(int b=7;b>0;b--)
	{
		dp[b][2]=++c;
		pt[c]={b,2};
		// cout<<c<<" represent "<<b<<' '<<2<<endl;
		dp[b][1]=++c; // odd
		// cout<<c<<" represent bit: "<<b<<" val "<<1<<endl;
		pt[c]={b,1};
		// cout<<c<<" represent "<<b<<' '<<1<<endl;
		dp[b][0]=++c; // even
		// cout<<c<<" represent bit: "<<b<<" val "<<0<<endl;
		pt[c]={b,0};
		// cout<<c<<" represent "<<b<<' '<<0<<endl;
	}
	pt[0]={8,0};
	// B's 0th bit in base-3 is zero
	// A's 0th bit will be greater than 0 thus b is smaller
	dp[0][0]=-2; // B smaller 

	dp[0][2]=-1; // A smaller


	dp[0][1]=++c; // B smaller
	pt[c]={0,1};
	// cout<<c<<" represent "<<0<<' '<<1<<endl;
	// cout<<c<<endl;
	// return {{}};
	vector<vector<int>> s;
	for(int i=0;i<=c;i++)
	{
		s.push_back({});
		// if(i==0) // start by checking the bit in a
		// {
		// 	s[i].push_back(0);
		// 	int bit=12; // check A
		// 	// number bit from 13 to 1
		// 	for(int result=1;result<=N;result++)
		// 	{
		// 		bool p=(result&(1<<bit)); // checking bit 12
		// 		s[i].push_back(dp[bit][p]);
		// 		// even * 2 == multiple of four
		// 		// cout<<"For "<<i<<' '<<result<<' '<<(check*2)+p<<endl;;
		// 	}
		// 	continue;
		// }
		int bit=pt[i].first;
		int val=pt[i].second;
		// this bit as calculated last time
		// cout<<"Statergy if "<<i<<" on board "<<bit<<' '<<val<<endl;
		int cbit=bit-1;
		if(bit%2==1) // now check bit in b
		{
			// cout<<"Ask Bag B"<<endl;
			// checking bag B
			s[i].push_back(1);
			int oth=val;
			for(int result=1;result<=N;result++)
			{
				int p=findbitvalue(result,bit);
				// cout<<" If res = "<<result<<" bit "<<p<<endl;
				if(oth>p) // bit smaller than the other
				{
					// cout<<-2<<' ';
					s[i].push_back(-2); // B smaller
				}
				else if(oth<p) // greater than the other
				{
					// cout<<-1<<' ';
					s[i].push_back(-1); // A smaller
				}
				else
				{
					p=findbitvalue(result,cbit);
					// cout<<"cbit val "<<p<<" transition "<<dp[cbit][p]<<endl;
					s[i].push_back(dp[cbit][p]);
				}
			}
		}
		else// now check bit in a
		{
			// cout<<"Ask Bag A"<<endl;
			s[i].push_back(0);
			int oth=val;
			for(int result=1;result<=N;result++)
			{
				int p=findbitvalue(result,bit);
				if(oth>p)
				{
					// cout<<-1<<' ';
					s[i].push_back(-1);
				}
				else if(oth<p)
				{
					// cout<<-2<<' ';
					s[i].push_back(-2);
				}
				else if(cbit>=0)
				{
					p=findbitvalue(result,cbit);
					// cout<<dp[cbit][p]<<' ';
					s[i].push_back(dp[cbit][p]);
				}
				else
				{
					s[i].push_back(-1);
				}
			}
			// cout<<endl;
		}
	}
	return s;
}

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