| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 128875 |
2019-07-11T10:33:16 Z |
youngyojun |
Rope (JOI17_rope) |
C++11 |
|
26 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 = N, c = 0; i; i--)
for(int v : G[i]) O[++c] = v;
for(int i = 0; i <= N; 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23924 KB |
Output is correct |
| 8 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 13 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 14 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 15 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 16 |
Correct |
23 ms |
23804 KB |
Output is correct |
| 17 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 18 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 19 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 22 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23924 KB |
Output is correct |
| 8 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 13 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 14 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 15 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 16 |
Correct |
23 ms |
23804 KB |
Output is correct |
| 17 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 18 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 19 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 22 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23924 KB |
Output is correct |
| 8 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 13 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 14 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 15 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 16 |
Correct |
23 ms |
23804 KB |
Output is correct |
| 17 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 18 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 19 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 22 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23924 KB |
Output is correct |
| 8 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 13 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 14 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 15 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 16 |
Correct |
23 ms |
23804 KB |
Output is correct |
| 17 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 18 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 19 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 22 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23924 KB |
Output is correct |
| 8 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 13 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 14 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 15 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 16 |
Correct |
23 ms |
23804 KB |
Output is correct |
| 17 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 18 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 19 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 22 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
