| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 243640 |
2020-07-01T13:01:55 Z |
TadijaSebez |
RLE (BOI06_rle) |
C++11 |
|
2500 ms |
117132 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<pair<int,set<int>>> groups;
void Check()
{
for(int i=0;i<groups.size();i++)
{
if(groups[i].second.empty())
{
swap(groups[i],groups[groups.size()-1]);
groups.pop_back();
return;
}
}
}
unordered_map<int,int> change[N];
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;
}
void Solve()
{
groups.pb({0,{0}});
set<int> tmp;
for(int i=1;i<n;i++) tmp.insert(i),change[i][-1]=0;
groups.pb({3,tmp});
for(int tm=0;tm<seq.size();tm++)
{
int x=seq[tm].first;
ll sz=seq[tm].second;
//printf("(%i %i) ",x,sz);
int dp;
for(int i=0;i<groups.size();i++)
{
if(groups[i].second.count(x))
{
dp=groups[i].first;
groups[i].second.erase(x);
if(groups[i].second.empty()){
for(int j=i+1;j<groups.size();j++)groups[j-1]=groups[j];
groups.pop_back();
}
}
}
Check();
int c1=Calc1(sz);
int c2=Calc2(sz);
int mn=0;
for(int i=0;i<groups.size();i++)
{
groups[i].first+=c2;
if(i==0 || groups[mn].first>groups[i].first) mn=i;
}
if(groups[mn].first+3<dp+c1)
{
change[x][tm]=*groups[mn].second.begin();
dp=groups[mn].first+3;
}
else dp+=c1;
bool ok=0;
for(int i=0;i<groups.size();i++) if(groups[i].first==dp)
{
groups[i].second.insert(x);
ok=1;
break;
}
if(!ok) groups.pb({dp,{x}});
}
}
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 mn=0;
for(int i=0;i<groups.size();i++) if(i==0 || groups[mn].first>groups[i].first) mn=i;
int key=*groups[mn].second.begin();
for(int i=seq.size()-1;i>=0;i--)
{
//printf("\ni:%i key:%i",i,key);
if(change[key].count(i))
{
int nKey=change[key][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 Check()':
rle.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++)
~^~~~~~~~~~~~~~
rle.cpp: In function 'void Solve()':
rle.cpp:77:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int tm=0;tm<seq.size();tm++)
~~^~~~~~~~~~~
rle.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++)
~^~~~~~~~~~~~~~
rle.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i+1;j<groups.size();j++)groups[j-1]=groups[j];
~^~~~~~~~~~~~~~
rle.cpp:99:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++)
~^~~~~~~~~~~~~~
rle.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++) if(groups[i].first==dp)
~^~~~~~~~~~~~~~
rle.cpp: In function 'void Encrypt()':
rle.cpp:158:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++) if(i==0 || groups[mn].first>groups[i].first) mn=i;
~^~~~~~~~~~~~~~
rle.cpp: In function 'int main()':
rle.cpp:181: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:176: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:177: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]);
~~~~~^~~~~~~~~~~~
rle.cpp: In function 'void Solve()':
rle.cpp:82:7: warning: 'dp' may be used uninitialized in this function [-Wmaybe-uninitialized]
int dp;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5760 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5760 KB |
Output is correct |
| 3 |
Correct |
9 ms |
5760 KB |
Output is correct |
| 4 |
Correct |
11 ms |
5888 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5888 KB |
Output is correct |
| 6 |
Correct |
38 ms |
7920 KB |
Output is correct |
| 7 |
Correct |
228 ms |
19484 KB |
Output is correct |
| 8 |
Correct |
304 ms |
23940 KB |
Output is correct |
| 9 |
Correct |
645 ms |
51516 KB |
Output is correct |
| 10 |
Correct |
230 ms |
18908 KB |
Output is correct |
| 11 |
Correct |
181 ms |
16876 KB |
Output is correct |
| 12 |
Correct |
735 ms |
49616 KB |
Output is correct |
| 13 |
Correct |
508 ms |
36764 KB |
Output is correct |
| 14 |
Correct |
264 ms |
24412 KB |
Output is correct |
| 15 |
Correct |
151 ms |
15972 KB |
Output is correct |
| 16 |
Correct |
493 ms |
39516 KB |
Output is correct |
| 17 |
Correct |
724 ms |
45756 KB |
Output is correct |
| 18 |
Correct |
1002 ms |
60480 KB |
Output is correct |
| 19 |
Execution timed out |
2598 ms |
81816 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2575 ms |
117132 KB |
Time limit exceeded |
