Submission #938417

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938417	2024-03-05T06:16:24 Z	aaron_dcoder	Shift (POI11_prz)	C++17	100 / 100	165 ms	48092 KB

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = int; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
//constexpr ll INFTY = 2e18;

ll N;


ll find_remove(ll to_rem, deque<ll>& find_in, deque<ll>& temp)
{
	swap(find_in,temp);
	find_in.resize(temp.size()-1);
	ll i;
	for (i = 0; temp[i]!=to_rem; ++i)
	{
		find_in[i] = temp[i];	
	}
	for (ll j = i; j < ll(find_in.size()); ++j)
	{
		find_in[j] = temp[j+1];
	}
	return i;
}

int main()
{
	cin >> N;

	vector<ll> P(N);
	for (ll i = 0; i < N; ++i)
	{
		cin >> P[i];
	}

	if (N==1) {
		cout << "0";
		return 0;
	}


	vector<pair<ll,char>> outp;

	deque<ll> remain(P.cbegin(),P.cend());
	deque<ll> temp;
	ll curr=1;

	while (remain.size()>2)
	{
		ll i = find_remove(curr, remain, temp);
		outp.push_back({-i,'a'});

		for (; i > 1; i-=2)
		{
			outp.push_back({2,'a'}); 
			outp.push_back({1,'b'}); 
		}
		if (i==1)
		{
			outp.push_back({1,'a'});
			outp.push_back({2,'b'});
			swap(remain[0],remain[1]);
			i--;
		}
		assert(i==0);
		outp.push_back({-1,'a'});
		curr++;
	}

	if (remain[0]==N-1)
	{
		outp.push_back({-2,'a'});
	}
	else 
	{
		assert(remain[0]==N);
		dbgv("g");

		if (N%2==1)
		{
			cout << "NIE DA SIE";
			return 0;
		}
		for (ll i = 0; i < (N/2)-1; ++i)
		{
			outp.push_back({2,'a'}); 
			outp.push_back({1,'b'});
		}
		outp.push_back({-1,'a'});
	}

	for (ll fff=0;fff<2;fff++)
	{
		vector<pair<ll,char>> newoutp;
			pair<ll,char> currcmd={0,'z'};
		for (pair<ll,char> cmd : outp)
		{
			dbgv(cmd.e0 << cmd.e1);
			if (cmd.e1==currcmd.e1) currcmd.e0+=cmd.e0;
			else
			{
				if (currcmd.e0!=0){
					newoutp.push_back({currcmd.e0, currcmd.e1});
				}
				currcmd=cmd;
			}
			if (currcmd.e1=='a') {
				currcmd.e0+=2*N;
				currcmd.e0%=N;
			}
			else 
			{
				currcmd.e0+=6;
				currcmd.e0%=3;
			}
		}
		if (currcmd.e0!=0){
			newoutp.push_back({currcmd.e0, currcmd.e1});
		}
		swap(outp,newoutp);
	}

	stringstream stroutp;
	ll osize = 0;
	{
		pair<ll,char> currcmd={0,'z'};
		for (pair<ll,char> cmd : outp)
		{
			dbgv(cmd.e0 << cmd.e1);
			if (cmd.e1==currcmd.e1) currcmd.e0+=cmd.e0;
			else
			{
				if (currcmd.e0!=0){
					osize+=1;
					stroutp << currcmd.e0 << currcmd.e1 << " ";
				}
				currcmd=cmd;
			}
			if (currcmd.e1=='a') {
				currcmd.e0+=2*N;
				currcmd.e0%=N;
			}
			else 
			{
				currcmd.e0+=6;
				currcmd.e0%=3;
			}
		}
		if (currcmd.e0!=0){
			osize+=1;
			stroutp << currcmd.e0 << currcmd.e1 << " ";
		}
}
	cout << osize << "\n";
	cout << stroutp.str();
}

Subtask #1
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	608 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	1896 KB	Output is correct
2	Correct	6 ms	1904 KB	Output is correct
3	Correct	7 ms	1880 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	20968 KB	Output is correct
2	Correct	59 ms	19848 KB	Output is correct
3	Correct	62 ms	19180 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	23296 KB	Output is correct
2	Correct	73 ms	23480 KB	Output is correct
3	Correct	70 ms	23824 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	23992 KB	Output is correct
2	Correct	88 ms	24480 KB	Output is correct
3	Correct	165 ms	48092 KB	Output is correct
4	Correct	5 ms	348 KB	Output is correct
5	Correct	11 ms	4556 KB	Output is correct

Submission #938417

Compilation message