답안 #199461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199461 2020-02-01T12:57:14 Z TadijaSebez RLE (BOI06_rle) C++11
85 / 100
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;
       ^~
# 결과 실행 시간 메모리 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