답안 #137709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137709	2019-07-28T08:52:07 Z	김현수(#3360)	RLE (BOI06_rle)	C++14	컴파일 오류	0 ms	0 KB

rle

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
const int N = 2000005, L = 131072, inf = 1e9;

int m, n, rn, a[N], c[N], wh[L], sw[N], crm;
vector<int> ans;

int cost1 (int L) {return (L+m-1)/m*3;}

void make1 (int L) {
	while(L) {
		int C = min(m-1, L-1);
		ans.push_back(C);
		ans.push_back(crm);
		ans.push_back(crm);
		L -= C+1;
	}
}

int cost2 (int L) {
	int R = L%(m+2);
	if(R == 0 || R > 2) return (L+m+1)/(m+2)*3;
	else return L/(m+2)*3+R;
}

void make2 (int L, int I) {
	while(L >= 3) {
		int C = min(m-1, L-3);
		ans.push_back(C);
		ans.push_back(I);
		ans.push_back(crm);
		L -= C + 3;
	}
	while(L) {
		ans.push_back(I);
		L--;
	}
}

struct segtree {
	pii v[2*L];
	void init () {
		for(int i=1;i<m;i++) {
			v[i+L] = {3, i};
		}
		for(int i=L;--i;) {
			v[i] = min(v[2*i], v[2*i+1]);
		}
	}
	void upd (int P, int V) {
		P += L; v[P].X += V; P /= 2;
		while(P) {
			v[P] = min(v[2*P], v[2*P+1]);
			P /= 2;
		}
	}
	pii get (int S, int E) {
		S += L; E += L;
		pii R = {inf, inf};
		while(S <= E) {
			if(S%2 == 1) R = min(R, v[S++]);
			if(E%2 == 0) R = min(R, v[E--]);
			S /= 2; E /= 2;
		}
		return R;
	}
} seg;

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++) {
		int T;
		scanf("%d",&T);
		if(!rn || a[T] != a[rn]) rn++;
		a[rn] = T;
		c[rn]++;
	}
	for(int i=1;i<=m;i++) {
		wh[i] = 3;
	}
	seg.init();
	for(int i=1;i<=rn;i++) {
		int X = cost1(c[i]) - cost2(c[i]);
		auto V1 = min(seg.get(0, a[i]-1), seg.get(a[i]+1, m-1)), V2 = seg.get(a[i], a[i]);
		if(X > V1.X - V2.X + 3) {
			seg.upd(a[i], V1.X - V2.X + 3);
			sw[i] = V1.Y;
		}
		else seg.upd(a[i], X);
	}
	crm = seg.get(0, m-1).Y;
	for(int i=rn;i>=1;i--) {
		if(crm == a[i] && sw[i]) swit(sw[i]);
		if(crm == a[i]) make1(c[i]);
		else make2(c[i], a[i]);
	}
	if(crm != 0) swit(0);
	printf("%d\n", ans.size());
	for(int i=ans.size();i--;) {
		printf("%d ", ans[i]);
	}
}

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:98:28: error: 'swit' was not declared in this scope
   if(crm == a[i] && sw[i]) swit(sw[i]);
                            ^~~~
rle.cpp:98:28: note: suggested alternative: 'sw'
   if(crm == a[i] && sw[i]) swit(sw[i]);
                            ^~~~
                            sw
rle.cpp:102:15: error: 'swit' was not declared in this scope
  if(crm != 0) swit(0);
               ^~~~
rle.cpp:102:15: note: suggested alternative: 'sw'
  if(crm != 0) swit(0);
               ^~~~
               sw
rle.cpp:103:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
rle.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
  ~~~~~^~~~~~~~~~~~~~
rle.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~