Submission #243667

#	Time	Username	Problem	Language	Result	Execution time	Memory
243667		TadijaSebez	RLE (BOI06_rle)	C++11	100 / 100	644 ms	78616 KiB

rle

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=100050;
const int M=2000050;
int a[M],n,m;
vector<pair<int,ll>> seq;
void push(int x,ll 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);
	}
}
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],nxt[N],prv[N],add,mn;
bool cng[M];
int go[M];
void Solve(){
	for(int i=0;i<n+4;i++)nxt[i]=prv[i]=-1;
	dp[0]=0;nxt[n+0]=0;prv[0]=n+0;
	int las=n+3;
	for(int i=1;i<n;i++){
		dp[i]=3;
		nxt[las]=i;
		prv[i]=las;
		las=i;
	}
	for(int tm=0;tm<seq.size();tm++){
		int x=seq[tm].first;
		ll sz=seq[tm].second;
		int c1=Calc1(sz);
		int c2=Calc2(sz);
		dp[x]+=add;
		int a=prv[x],b=nxt[x];
		if(~a)nxt[a]=b;
		if(~b)prv[b]=a;
		nxt[x]=prv[x]=-1;
		add+=c2;mn+=c2;
		int mnp,now;
		for(int i=0;i<4;i++)if(nxt[n+i]!=-1){mnp=nxt[n+i];now=mn+i;break;}
		if(dp[x]+c1<=now+3){
			dp[x]+=c1;
			cng[tm]=false;
		}else{
			dp[x]=now+3;
			cng[tm]=true;
			go[tm]=mnp;
		}
		int my=dp[x]-mn;
		while(my>3){
			mn++;
			for(int i=0;i<3;i++){
				if(~nxt[n+i+1])prv[nxt[n+i+1]]=n+i;
				nxt[n+i]=nxt[n+i+1];
			}
			nxt[n+3]=-1;
			my--;
		}
		dp[x]-=add;
		nxt[x]=nxt[n+my];
		prv[x]=n+my;
		if(~nxt[n+my])prv[nxt[n+my]]=x;
		nxt[n+my]=x;
		while(nxt[n+0]==-1){
			mn++;
			for(int i=0;i<3;i++){
				if(~nxt[n+i+1])prv[nxt[n+i+1]]=n+i;
				nxt[n+i]=nxt[n+i+1];
			}
			nxt[n+3]=-1;
		}
	}
}
void Add(int key,int x,ll sz){
	while(sz>0){
		if(key==x){
			int l=min(sz,(ll)n);
			ans.pb(l-1);
			ans.pb(x);
			ans.pb(key);
			sz-=l;
		}else{
			if(sz<=3){
				while(sz--)ans.pb(x);
			}else{
				int l=min(sz,(ll)n+2);
				ans.pb(l-3);
				ans.pb(x);
				ans.pb(key);
				sz-=l;
			}
		}
	}
}
void ChangeKey(int x,int y){
	ans.pb(0);
	ans.pb(y);
	ans.pb(x);
}
void Encrypt(){
	int key=nxt[n+0];
	for(int i=seq.size()-1;i>=0;i--){
		if(key==seq[i].first&&cng[i]){
			int nKey=go[i];
			ChangeKey(nKey,key);
			key=nKey;
		}
		Add(key,seq[i].first,seq[i].second);
	}
	if(key!=0)ChangeKey(0,key);
	reverse(ans.begin(),ans.end());
}
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:58: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:149: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:144: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:145:28: 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]);
                       ~~~~~^~~~~~~~~~~~
rle.cpp: In function 'void Solve()':
rle.cpp:71:19: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(dp[x]+c1<=now+3){
                ~~~^~
rle.cpp:77:10: warning: 'mnp' may be used uninitialized in this function [-Wmaybe-uninitialized]
    go[tm]=mnp;
    ~~~~~~^~~~

• Subtask 1: 100 / 100