oj.uz

Submission #128874

# Submission time Handle Problem Language Result Execution time Memory
128874 2019-07-11T10:32:20 Z youngyojun Rope (JOI17_rope) C++11
0 / 100
 24 ms 23928 KB 
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

const int MAXN = 1000055;

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

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

int N, M;

int main() {
	ios::sync_with_stdio(false);

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Incorrect 23 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Incorrect 23 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Incorrect 23 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Incorrect 23 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Incorrect 23 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -