Submission #122878

#	Time	Username	Problem	Language	Result	Execution time	Memory
122878		arthurconmy	Linear Garden (IOI08_linear_garden)	C++14	40 / 100	9 ms	2452 KiB

linear_garden

/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) for (int j = int(d); j >= int(c); j--)
#define ff first
#define ss second
#define pb push_back
#define len(x) int((x).size())
#define endl "\n"

int main() // LL OR INT?? DELETED IFSTREAM??
{
	#ifdef LOCAL
		ifstream cin("input.txt");
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin>>n>>m;
	string s;
	cin>>s;

	int a=1;
	int b=0;
	int c=1;

	int cur=1; // cur is placement in CURRENT group ??? YES
	char cur_group;

	if(s[0]=='L')
	{
		cur_group='a';
	}

	if(s[0]=='P')
	{
		cur_group='c';
	}

	REP(i,1,n-1)
	{
		//cout << i << " " << cur << " " << cur_group << endl;

		if(i%2 == 1)
		{
			int new_a = 2*a - 1;
			int new_b = b+2;
			int new_c = 2*c - 1;

			if(cur_group == 'a')
			{
				if(cur==a && s[i]=='P')
				{
					cur=1;
					cur_group='b';

					a=new_a;
					b=new_b;
					c=new_c;

					continue;
				}

				cur = cur*2;
				if(s[i]=='L') cur--;

				a=new_a;
				b=new_b;
				c=new_c;

				continue;
			}

			if(cur_group=='b')
			{
				cur++;

				a=new_a;
				b=new_b;
				c=new_c;

				continue;
			}

			if(cur_group=='c')
			{
				if(cur==1 && s[i]=='L')
				{
					cur_group='b';
					cur=new_b;

					a=new_a;
					b=new_b;
					c=new_c;

					continue;
				}

				cur = cur*2;
				cur--;
				if(s[i]=='L') cur--;

				a=new_a;
				b=new_b;
				c=new_c;

				continue;
			}
		}

		if(i%2==0)
		{
			int new_a = a + 1;
			int new_b = 2*b - 2;
			int new_c = c + 1;

			if(cur_group=='a')
			{
				a=new_a;
				b=new_b;
				c=new_c;

				continue;
			}

			if(cur_group=='b')
			{
				if(cur==1 && s[i]=='L')
				{
					cur=a+1;
					cur_group='a';
					
					a=new_a;
					b=new_b;
					c=new_c;

					continue;
				}

				if(cur==b && s[i]=='P')
				{
					cur=1;
					cur_group='c';

					a=new_a;
					b=new_b;
					c=new_c;

					continue;
				}

				// otherwise we'll remain in B

				cur = 2*(cur-1);
				if(s[i]=='P') cur++;

				a=new_a;
				b=new_b;
				c=new_c;

				continue;
			}

			if(cur_group=='c')
			{
				cur++;

				a=new_a;
				b=new_b;
				c=new_c;

				continue;
			}
		}
	}

	//cout << a << " " << b << " " << c << endl << endl;

	//cout << cur << " " << cur_group << endl;

	if(cur_group=='a')
	{
		cout << cur%m << endl;
	}

	if(cur_group=='b')
	{
		cout << (cur + a)%m << endl;
	}

	if(cur_group=='c')
	{
		cout << (cur + a + b)%m << endl;
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5