| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199461 |
2020-02-01T12:57:14 Z |
TadijaSebez |
RLE (BOI06_rle) |
C++11 |
|
2500 ms |
80828 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int M=2000050;
int a[M],n,m;
vector<pair<int,int>> 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);
}
}
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;
}
}
}
map<int,int> change[N];
vector<int> ans;
int Calc1(int sz)
{
int cnt=0;
while(sz>0)
{
cnt+=3;
sz-=n;
}
return cnt;
}
int Calc2(int 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;
int 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);
}
}
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, int sz)
{
while(sz>0)
{
if(key==x)
{
int l=min(sz,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,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:37: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:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int tm=0;tm<seq.size();tm++)
~~^~~~~~~~~~~
rle.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++)
~^~~~~~~~~~~~~~
rle.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<groups.size();i++)
~^~~~~~~~~~~~~~
rle.cpp:106: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:153: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:176: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:171: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:172: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:81:7: warning: 'dp' may be used uninitialized in this function [-Wmaybe-uninitialized]
int dp;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
11 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
34 ms |
6772 KB |
Output is correct |
| 7 |
Correct |
215 ms |
16356 KB |
Output is correct |
| 8 |
Correct |
278 ms |
19856 KB |
Output is correct |
| 9 |
Correct |
542 ms |
37716 KB |
Output is correct |
| 10 |
Correct |
201 ms |
16200 KB |
Output is correct |
| 11 |
Correct |
175 ms |
13408 KB |
Output is correct |
| 12 |
Correct |
532 ms |
34500 KB |
Output is correct |
| 13 |
Correct |
456 ms |
30036 KB |
Output is correct |
| 14 |
Correct |
298 ms |
18816 KB |
Output is correct |
| 15 |
Correct |
149 ms |
12552 KB |
Output is correct |
| 16 |
Correct |
454 ms |
30540 KB |
Output is correct |
| 17 |
Correct |
640 ms |
35656 KB |
Output is correct |
| 18 |
Incorrect |
799 ms |
36060 KB |
the output code does not encode the input sequence |
| 19 |
Execution timed out |
2560 ms |
48672 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2562 ms |
80828 KB |
Time limit exceeded |
