Submission #128887

#	Time	Username	Problem	Language	Result	Execution time	Memory
128887		youngyojun	Rope (JOI17_rope)	C++11	100 / 100	988 ms	115904 KiB

rope

#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
using namespace std;
typedef unsigned int ui;
static unsigned char str[9900099], *p=str;

const int MAXN = 1000055;

ui D[MAXN][2];
bitset<MAXN> chk;

vector<int> G[MAXN];
vector<ui> T[MAXN];
ui O[MAXN];
ui A[MAXN], B[MAXN];

ui N, M;

int main() {
	fread(str, 1, 9900099, stdin);

	rf(N) rf(M)
	for(ui i = N; i; i--) {
		rf(A[i])
		B[A[i]]++;
	}
	for(ui i = M; i; i--) T[B[i]].eb(i);
	for(ui i = N, c = 0; i; i--)
		for(ui v : T[i]) O[++c] = v;
	for(int i = 1; i < N; i++) if(A[i] != A[i+1]) {
		G[A[i]].eb(i+1);
		G[A[i+1]].eb(-i);
	}

	for(ui i = 1; i <= M; i++) {
		int ret = 0, dg = 0;
		for(int v : G[i]) {
			D[A[v < 0 ? -v : v]][(0 < v ? v-1 : -v)&1]++;
			chk[A[v < 0 ? -v : v]] = true;
			dg++;
		}
		for(ui oi = 1, c; oi <= M && oi <= dg+2; oi++) {
			c = O[oi];
			if(c == i || chk[c]) continue;
			ret = -int(B[c]);
			break;
		}
		for(int v : G[i]) {
			int c = A[v < 0 ? -v : v], t = min(D[c][0], D[c][1]) - B[c];
			if(t < ret) ret = t;
		}
		for(int v : G[i]) {
			D[A[v < 0 ? -v : v]][(0 < v ? v-1 : -v)&1] = 0;
			chk[A[v < 0 ? -v : v]] = false;
		}
		printf("%d\n", ret + N-B[i]);
	}
	return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < N; i++) if(A[i] != A[i+1]) {
                 ~~^~~
rope.cpp:43:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ui oi = 1, c; oi <= M && oi <= dg+2; oi++) {
                                ~~~^~~~~~~
rope.cpp:21:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 9900099, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20