| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 243667 |
2020-07-01T14:08:50 Z |
TadijaSebez |
RLE (BOI06_rle) |
C++11 |
|
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;
~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
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 |
