답안 #243667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243667 2020-07-01T14:08:50 Z TadijaSebez RLE (BOI06_rle) C++11
100 / 100
644 ms 78616 KB
#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

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;
    ~~~~~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 27 ms 2044 KB Output is correct
7 Correct 191 ms 11360 KB Output is correct
8 Correct 263 ms 15076 KB Output is correct
9 Correct 397 ms 39996 KB Output is correct
10 Correct 179 ms 11360 KB Output is correct
11 Correct 150 ms 9948 KB Output is correct
12 Correct 282 ms 27856 KB Output is correct
13 Correct 418 ms 24144 KB Output is correct
14 Correct 123 ms 12764 KB Output is correct
15 Correct 66 ms 7012 KB Output is correct
16 Correct 454 ms 26192 KB Output is correct
17 Correct 479 ms 30028 KB Output is correct
18 Correct 452 ms 32832 KB Output is correct
19 Correct 622 ms 72732 KB Output is correct
20 Correct 644 ms 78616 KB Output is correct