Submission #199460

#	Time	Username	Problem	Language	Result	Execution time	Memory
199460		TadijaSebez	RLE (BOI06_rle)	C++11	80 / 100	2593 ms	61884 KiB

rle

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int M=2000050;
int a[M],n,m;
vector<pair<int,ll>> seq;
void push(int x, int sz)
{
	if(seq.size() && seq.back().first==x) seq[seq.size()-1].second+=sz;
	else seq.pb({x,sz});
}
void Decrypt()
{
	int key=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i]==key)
		{
			if(a[i+1]==key)
			{
				push(a[i+1],a[i+2]+1);
			}
			else
			{
				if(a[i+2]==0) key=a[i+1];
				else push(a[i+1],a[i+2]+3);
			}
			i+=2;
		}
		else push(a[i],1);
	}
}
int change[M];
vector<int> ans;
int Calc1(ll sz)
{
	int cnt=0;
	while(sz>0)
	{
		cnt+=3;
		sz-=n;
	}
	return cnt;
}
int Calc2(ll sz)
{
	int cnt=0;
	while(sz>0)
	{
		if(sz<=3) cnt+=sz;
		else cnt+=3;
		sz-=n+2;
	}
	return cnt;
}
int dp[N],lzy;
set<pair<int,int>> all;
void Solve()
{
	for(int i=1;i<n;i++) dp[i]=3;
	for(int i=0;i<n;i++) all.insert({dp[i],i});
	lzy=0;
	for(int tm=0;tm<seq.size();tm++)
	{
		change[tm]=-1;
		int x=seq[tm].first;
		ll sz=seq[tm].second;
 
		int k=-1;
		for(int j=0;j<n;j++) if(j!=x && (k==-1 || dp[k]>dp[j])) k=j;
		int c1=Calc1(sz);
		int c2=Calc2(sz);
		dp[x]+=c1;
		for(int j=0;j<n;j++) if(j!=x) dp[j]+=c2;
		if(dp[k]+3<dp[x]) dp[x]=dp[k]+3,change[tm]=k;
 
		/*all.erase({dp[x],x});
		int tmp=dp[x]+lzy;
		int c1=Calc1(sz);
		int c2=Calc2(sz);
		int mn,p;
		tie(mn,p)=*all.begin();
		mn+=lzy;
		if(mn+lzy+c2+3<tmp+c1)
		{
			change[tm]=p;
			tmp=mn+lzy+c2+3;
		}
		else tmp+=c1;
		lzy+=c2;
		dp[x]=tmp-lzy;
		all.insert({dp[x],x});*/
	}
}
void Add(int key, int x, ll sz)
{
	while(sz>0)
	{
		if(key==x)
		{
			int l=min(sz,(ll)n);
			ans.pb(key);
			ans.pb(x);
			ans.pb(l-1);
			sz-=l;
		}
		else
		{
			if(sz<=3)
			{
				while(sz--) ans.pb(x);
			}
			else
			{
				int l=min(sz,(ll)n+2);
				ans.pb(key);
				ans.pb(x);
				ans.pb(l-3);
				sz-=l;
			}
		}
	}
}
void ChangeKey(int x, int y)
{
	ans.pb(x);
	ans.pb(y);
	ans.pb(0);
}
void Encrypt()
{
	//int key=all.begin()->second;
	int key=0;
	for(int i=0;i<n;i++) if(dp[i]<dp[key]) key=i;
	vector<pair<int,pair<int,ll>>> op;
	for(int i=seq.size()-1;i>=0;i--)
	{
		if(seq[i].first==key && change[i]!=-1)
		{
			int nKey=change[i];
			//ChangeKey(nKey,key);
			op.pb({nKey,{key,-1}});
			key=nKey;
		}
		//Add(key,seq[i].first,seq[i].second);
		op.pb({key,{seq[i].first,seq[i].second}});
	}
	if(key!=0) op.pb({0,{key,-1}});//ChangeKey(0,key);
	reverse(op.begin(),op.end());
	for(auto o:op)
	{
		if(o.second.second==-1) ChangeKey(o.first,o.second.first);
		else Add(o.first,o.second.first,o.second.second);
	}
}
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++) scanf("%i",&a[i]);
	Decrypt();
	Solve();
	Encrypt();
	printf("%i\n",ans.size());
	for(int i:ans) printf("%i ",i);
	printf("\n");
	return 0;
}

Compilation message (stderr)

rle.cpp: In function 'void Solve()':
rle.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int tm=0;tm<seq.size();tm++)
               ~~^~~~~~~~~~~
rle.cpp: In function 'int main()':
rle.cpp:165:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%i\n",ans.size());
                ~~~~~~~~~~^
rle.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
rle.cpp:161:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i",&a[i]);
                        ~~~~~^~~~~~~~~~~~

• Subtask 1: 80 / 100