oj.uz

답안 #137740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137740 2019-07-28T09:18:57 Z 김현수(#3360) RLE (BOI06_rle) C++14
15 / 100
 1373 ms 524292 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define pii MyFuckingPair
using namespace std;

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

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

void append (int V, int C) {
	if(!rn || a[rn] != V) rn++;
	a[rn] = V;
	c[rn] += C;
}

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--;
	}
}

void swit (int I) {
	ans.push_back(0);
	ans.push_back(crm);
	ans.push_back(I);
	crm = I;
}

struct MyFuckingPair {
	int X, Y;
	bool operator < (const MyFuckingPair &T) const {
		if(X != T.X) return X < T.X;
		return Y < T.Y;
	}
};

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(T != crm) {
			append(T, 1);
			continue;
		}
		i += 2;
		int A, B;
		scanf("%d%d",&A,&B);
		if(T == A) append(A, B+1);
		else if(B) append(A, B+3);
		else crm = A;
	}
	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);
			sw[i] = -1;
		}
	}
	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:132: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:97: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:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
rle.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Incorrect 3 ms 1400 KB the output code does not encode the input sequence
3 Incorrect 3 ms 1400 KB the output code does not encode the input sequence
4 Incorrect 4 ms 1400 KB the output code does not encode the input sequence
5 Incorrect 4 ms 1400 KB the output code does not encode the input sequence
6 Incorrect 24 ms 2264 KB the output code does not encode the input sequence
7 Incorrect 170 ms 7684 KB the output code does not encode the input sequence
8 Incorrect 226 ms 10128 KB the output code does not encode the input sequence
9 Incorrect 399 ms 18608 KB Unexpected end of file - int32 expected
10 Incorrect 169 ms 7444 KB Unexpected end of file - int32 expected
11 Incorrect 140 ms 7140 KB the output code does not encode the input sequence
12 Incorrect 332 ms 15508 KB the output code does not encode the input sequence
13 Incorrect 371 ms 16448 KB the output code does not encode the input sequence
14 Incorrect 167 ms 7488 KB the output code does not encode the input sequence
15 Incorrect 91 ms 4588 KB the output code does not encode the input sequence
16 Incorrect 362 ms 17072 KB the output code does not encode the input sequence
17 Incorrect 466 ms 19920 KB the output code does not encode the input sequence
18 Runtime error 1245 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 1270 ms 45504 KB Output is correct
20 Correct 1373 ms 45520 KB Output is correct