| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199460 |
2020-02-01T12:56:19 Z |
TadijaSebez |
RLE (BOI06_rle) |
C++11 |
|
2500 ms |
61884 KB |
#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
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]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
388 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
6 ms |
504 KB |
Output is correct |
| 5 |
Correct |
6 ms |
504 KB |
Output is correct |
| 6 |
Correct |
30 ms |
2668 KB |
Output is correct |
| 7 |
Correct |
209 ms |
13700 KB |
Output is correct |
| 8 |
Correct |
272 ms |
19160 KB |
Output is correct |
| 9 |
Correct |
428 ms |
61884 KB |
Output is correct |
| 10 |
Correct |
220 ms |
12952 KB |
Output is correct |
| 11 |
Correct |
199 ms |
12648 KB |
Output is correct |
| 12 |
Correct |
379 ms |
41412 KB |
Output is correct |
| 13 |
Correct |
481 ms |
30996 KB |
Output is correct |
| 14 |
Correct |
1379 ms |
17308 KB |
Output is correct |
| 15 |
Correct |
2108 ms |
9316 KB |
Output is correct |
| 16 |
Correct |
502 ms |
31956 KB |
Output is correct |
| 17 |
Execution timed out |
2593 ms |
20192 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2537 ms |
24160 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2552 ms |
56596 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2507 ms |
56604 KB |
Time limit exceeded |
