#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
vector<int>V[LIM];
int ile[LIM], wynik[LIM], sum;
void dodaj(int x) {
if(x==-1) return;
++ile[x];
++sum;
}
void usun(int x) {
if(x==-1) return;
--ile[x];
--sum;
}
void solve(vector<pair<int,int>>T, int m) {
sum=0;
rep(i, m) {
V[i].clear();
ile[i]=0;
}
int n=T.size();
rep(i, n) {
V[T[i].st].pb(i);
if(T[i].nd!=-1 && T[i].nd!=T[i].st) V[T[i].nd].pb(i);
dodaj(T[i].st);
dodaj(T[i].nd);
}
rep(i, m) {
int akt=0;
for(auto j : V[i]) {
usun(T[j].st);
usun(T[j].nd);
if(T[j].st!=i) ++akt;
if(T[j].nd!=-1 && T[j].nd!=i) ++akt;
}
int ma=0;
rep(j, m) ma=max(ma, ile[j]);
wynik[i]=min(wynik[i], akt+sum-ma);
for(auto j : V[i]) {
dodaj(T[j].st);
dodaj(T[j].nd);
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
rep(i, m) wynik[i]=n;
vector<int>T(n);
rep(i, n) {
cin >> T[i]; --T[i];
}
vector<pair<int,int>>P;
if(n%2==0) {
rep(i, n/2) P.pb({T[2*i], T[2*i+1]});
solve(P, m);
P.clear();
P.pb({T[0], -1});
rep(i, n/2-1) P.pb({T[2*i+1], T[2*i+2]});
P.pb({T[n-1], -1});
solve(P, m);
} else {
rep(i, n/2) P.pb({T[2*i], T[2*i+1]});
P.pb({T[n-1], -1});
solve(P, m);
P.clear();
P.pb({T[0], -1});
rep(i, n/2) P.pb({T[2*i+1], T[2*i+2]});
solve(P, m);
}
rep(i, m) cout << wynik[i] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27480 KB |
Output is correct |
2 |
Correct |
6 ms |
27484 KB |
Output is correct |
3 |
Correct |
6 ms |
27316 KB |
Output is correct |
4 |
Correct |
6 ms |
27484 KB |
Output is correct |
5 |
Correct |
6 ms |
27492 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
6 ms |
27492 KB |
Output is correct |
8 |
Correct |
6 ms |
27484 KB |
Output is correct |
9 |
Correct |
6 ms |
27484 KB |
Output is correct |
10 |
Correct |
6 ms |
27484 KB |
Output is correct |
11 |
Correct |
6 ms |
27480 KB |
Output is correct |
12 |
Correct |
5 ms |
27484 KB |
Output is correct |
13 |
Correct |
6 ms |
27484 KB |
Output is correct |
14 |
Correct |
6 ms |
27484 KB |
Output is correct |
15 |
Correct |
6 ms |
27328 KB |
Output is correct |
16 |
Correct |
6 ms |
27484 KB |
Output is correct |
17 |
Correct |
6 ms |
27340 KB |
Output is correct |
18 |
Correct |
6 ms |
27484 KB |
Output is correct |
19 |
Correct |
6 ms |
27484 KB |
Output is correct |
20 |
Correct |
5 ms |
27484 KB |
Output is correct |
21 |
Correct |
6 ms |
27348 KB |
Output is correct |
22 |
Correct |
6 ms |
27492 KB |
Output is correct |
23 |
Correct |
6 ms |
27484 KB |
Output is correct |
24 |
Correct |
6 ms |
27488 KB |
Output is correct |
25 |
Correct |
6 ms |
27484 KB |
Output is correct |
26 |
Correct |
6 ms |
27484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27480 KB |
Output is correct |
2 |
Correct |
6 ms |
27484 KB |
Output is correct |
3 |
Correct |
6 ms |
27316 KB |
Output is correct |
4 |
Correct |
6 ms |
27484 KB |
Output is correct |
5 |
Correct |
6 ms |
27492 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
6 ms |
27492 KB |
Output is correct |
8 |
Correct |
6 ms |
27484 KB |
Output is correct |
9 |
Correct |
6 ms |
27484 KB |
Output is correct |
10 |
Correct |
6 ms |
27484 KB |
Output is correct |
11 |
Correct |
6 ms |
27480 KB |
Output is correct |
12 |
Correct |
5 ms |
27484 KB |
Output is correct |
13 |
Correct |
6 ms |
27484 KB |
Output is correct |
14 |
Correct |
6 ms |
27484 KB |
Output is correct |
15 |
Correct |
6 ms |
27328 KB |
Output is correct |
16 |
Correct |
6 ms |
27484 KB |
Output is correct |
17 |
Correct |
6 ms |
27340 KB |
Output is correct |
18 |
Correct |
6 ms |
27484 KB |
Output is correct |
19 |
Correct |
6 ms |
27484 KB |
Output is correct |
20 |
Correct |
5 ms |
27484 KB |
Output is correct |
21 |
Correct |
6 ms |
27348 KB |
Output is correct |
22 |
Correct |
6 ms |
27492 KB |
Output is correct |
23 |
Correct |
6 ms |
27484 KB |
Output is correct |
24 |
Correct |
6 ms |
27488 KB |
Output is correct |
25 |
Correct |
6 ms |
27484 KB |
Output is correct |
26 |
Correct |
6 ms |
27484 KB |
Output is correct |
27 |
Correct |
15 ms |
29524 KB |
Output is correct |
28 |
Correct |
14 ms |
29396 KB |
Output is correct |
29 |
Correct |
14 ms |
29656 KB |
Output is correct |
30 |
Correct |
14 ms |
29400 KB |
Output is correct |
31 |
Correct |
15 ms |
29524 KB |
Output is correct |
32 |
Correct |
14 ms |
29524 KB |
Output is correct |
33 |
Correct |
14 ms |
29404 KB |
Output is correct |
34 |
Correct |
14 ms |
29408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27480 KB |
Output is correct |
2 |
Correct |
6 ms |
27484 KB |
Output is correct |
3 |
Correct |
6 ms |
27316 KB |
Output is correct |
4 |
Correct |
6 ms |
27484 KB |
Output is correct |
5 |
Correct |
6 ms |
27492 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
6 ms |
27492 KB |
Output is correct |
8 |
Correct |
6 ms |
27484 KB |
Output is correct |
9 |
Correct |
6 ms |
27484 KB |
Output is correct |
10 |
Correct |
6 ms |
27484 KB |
Output is correct |
11 |
Correct |
6 ms |
27480 KB |
Output is correct |
12 |
Correct |
5 ms |
27484 KB |
Output is correct |
13 |
Correct |
6 ms |
27484 KB |
Output is correct |
14 |
Correct |
6 ms |
27484 KB |
Output is correct |
15 |
Correct |
6 ms |
27328 KB |
Output is correct |
16 |
Correct |
6 ms |
27484 KB |
Output is correct |
17 |
Correct |
6 ms |
27340 KB |
Output is correct |
18 |
Correct |
6 ms |
27484 KB |
Output is correct |
19 |
Correct |
6 ms |
27484 KB |
Output is correct |
20 |
Correct |
5 ms |
27484 KB |
Output is correct |
21 |
Correct |
6 ms |
27348 KB |
Output is correct |
22 |
Correct |
6 ms |
27492 KB |
Output is correct |
23 |
Correct |
6 ms |
27484 KB |
Output is correct |
24 |
Correct |
6 ms |
27488 KB |
Output is correct |
25 |
Correct |
6 ms |
27484 KB |
Output is correct |
26 |
Correct |
6 ms |
27484 KB |
Output is correct |
27 |
Correct |
15 ms |
29524 KB |
Output is correct |
28 |
Correct |
14 ms |
29396 KB |
Output is correct |
29 |
Correct |
14 ms |
29656 KB |
Output is correct |
30 |
Correct |
14 ms |
29400 KB |
Output is correct |
31 |
Correct |
15 ms |
29524 KB |
Output is correct |
32 |
Correct |
14 ms |
29524 KB |
Output is correct |
33 |
Correct |
14 ms |
29404 KB |
Output is correct |
34 |
Correct |
14 ms |
29408 KB |
Output is correct |
35 |
Correct |
17 ms |
29520 KB |
Output is correct |
36 |
Correct |
16 ms |
29524 KB |
Output is correct |
37 |
Correct |
16 ms |
29524 KB |
Output is correct |
38 |
Correct |
16 ms |
29524 KB |
Output is correct |
39 |
Correct |
16 ms |
29776 KB |
Output is correct |
40 |
Correct |
15 ms |
29660 KB |
Output is correct |
41 |
Correct |
15 ms |
29672 KB |
Output is correct |
42 |
Correct |
15 ms |
29656 KB |
Output is correct |
43 |
Correct |
15 ms |
29660 KB |
Output is correct |
44 |
Correct |
17 ms |
29660 KB |
Output is correct |
45 |
Correct |
17 ms |
29660 KB |
Output is correct |
46 |
Correct |
17 ms |
29660 KB |
Output is correct |
47 |
Correct |
15 ms |
29660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27480 KB |
Output is correct |
2 |
Correct |
6 ms |
27484 KB |
Output is correct |
3 |
Correct |
6 ms |
27316 KB |
Output is correct |
4 |
Correct |
6 ms |
27484 KB |
Output is correct |
5 |
Correct |
6 ms |
27492 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
6 ms |
27492 KB |
Output is correct |
8 |
Correct |
6 ms |
27484 KB |
Output is correct |
9 |
Correct |
6 ms |
27484 KB |
Output is correct |
10 |
Correct |
6 ms |
27484 KB |
Output is correct |
11 |
Correct |
6 ms |
27480 KB |
Output is correct |
12 |
Correct |
5 ms |
27484 KB |
Output is correct |
13 |
Correct |
6 ms |
27484 KB |
Output is correct |
14 |
Correct |
6 ms |
27484 KB |
Output is correct |
15 |
Correct |
6 ms |
27328 KB |
Output is correct |
16 |
Correct |
6 ms |
27484 KB |
Output is correct |
17 |
Correct |
6 ms |
27340 KB |
Output is correct |
18 |
Correct |
6 ms |
27484 KB |
Output is correct |
19 |
Correct |
6 ms |
27484 KB |
Output is correct |
20 |
Correct |
5 ms |
27484 KB |
Output is correct |
21 |
Correct |
6 ms |
27348 KB |
Output is correct |
22 |
Correct |
6 ms |
27492 KB |
Output is correct |
23 |
Correct |
6 ms |
27484 KB |
Output is correct |
24 |
Correct |
6 ms |
27488 KB |
Output is correct |
25 |
Correct |
6 ms |
27484 KB |
Output is correct |
26 |
Correct |
6 ms |
27484 KB |
Output is correct |
27 |
Correct |
15 ms |
29524 KB |
Output is correct |
28 |
Correct |
14 ms |
29396 KB |
Output is correct |
29 |
Correct |
14 ms |
29656 KB |
Output is correct |
30 |
Correct |
14 ms |
29400 KB |
Output is correct |
31 |
Correct |
15 ms |
29524 KB |
Output is correct |
32 |
Correct |
14 ms |
29524 KB |
Output is correct |
33 |
Correct |
14 ms |
29404 KB |
Output is correct |
34 |
Correct |
14 ms |
29408 KB |
Output is correct |
35 |
Correct |
17 ms |
29520 KB |
Output is correct |
36 |
Correct |
16 ms |
29524 KB |
Output is correct |
37 |
Correct |
16 ms |
29524 KB |
Output is correct |
38 |
Correct |
16 ms |
29524 KB |
Output is correct |
39 |
Correct |
16 ms |
29776 KB |
Output is correct |
40 |
Correct |
15 ms |
29660 KB |
Output is correct |
41 |
Correct |
15 ms |
29672 KB |
Output is correct |
42 |
Correct |
15 ms |
29656 KB |
Output is correct |
43 |
Correct |
15 ms |
29660 KB |
Output is correct |
44 |
Correct |
17 ms |
29660 KB |
Output is correct |
45 |
Correct |
17 ms |
29660 KB |
Output is correct |
46 |
Correct |
17 ms |
29660 KB |
Output is correct |
47 |
Correct |
15 ms |
29660 KB |
Output is correct |
48 |
Correct |
127 ms |
50344 KB |
Output is correct |
49 |
Correct |
126 ms |
50468 KB |
Output is correct |
50 |
Correct |
130 ms |
50536 KB |
Output is correct |
51 |
Correct |
112 ms |
50300 KB |
Output is correct |
52 |
Correct |
107 ms |
48776 KB |
Output is correct |
53 |
Correct |
120 ms |
49604 KB |
Output is correct |
54 |
Correct |
119 ms |
48532 KB |
Output is correct |
55 |
Correct |
115 ms |
48328 KB |
Output is correct |
56 |
Correct |
113 ms |
48168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
27480 KB |
Output is correct |
2 |
Correct |
6 ms |
27484 KB |
Output is correct |
3 |
Correct |
6 ms |
27316 KB |
Output is correct |
4 |
Correct |
6 ms |
27484 KB |
Output is correct |
5 |
Correct |
6 ms |
27492 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
6 ms |
27492 KB |
Output is correct |
8 |
Correct |
6 ms |
27484 KB |
Output is correct |
9 |
Correct |
6 ms |
27484 KB |
Output is correct |
10 |
Correct |
6 ms |
27484 KB |
Output is correct |
11 |
Correct |
6 ms |
27480 KB |
Output is correct |
12 |
Correct |
5 ms |
27484 KB |
Output is correct |
13 |
Correct |
6 ms |
27484 KB |
Output is correct |
14 |
Correct |
6 ms |
27484 KB |
Output is correct |
15 |
Correct |
6 ms |
27328 KB |
Output is correct |
16 |
Correct |
6 ms |
27484 KB |
Output is correct |
17 |
Correct |
6 ms |
27340 KB |
Output is correct |
18 |
Correct |
6 ms |
27484 KB |
Output is correct |
19 |
Correct |
6 ms |
27484 KB |
Output is correct |
20 |
Correct |
5 ms |
27484 KB |
Output is correct |
21 |
Correct |
6 ms |
27348 KB |
Output is correct |
22 |
Correct |
6 ms |
27492 KB |
Output is correct |
23 |
Correct |
6 ms |
27484 KB |
Output is correct |
24 |
Correct |
6 ms |
27488 KB |
Output is correct |
25 |
Correct |
6 ms |
27484 KB |
Output is correct |
26 |
Correct |
6 ms |
27484 KB |
Output is correct |
27 |
Correct |
15 ms |
29524 KB |
Output is correct |
28 |
Correct |
14 ms |
29396 KB |
Output is correct |
29 |
Correct |
14 ms |
29656 KB |
Output is correct |
30 |
Correct |
14 ms |
29400 KB |
Output is correct |
31 |
Correct |
15 ms |
29524 KB |
Output is correct |
32 |
Correct |
14 ms |
29524 KB |
Output is correct |
33 |
Correct |
14 ms |
29404 KB |
Output is correct |
34 |
Correct |
14 ms |
29408 KB |
Output is correct |
35 |
Correct |
17 ms |
29520 KB |
Output is correct |
36 |
Correct |
16 ms |
29524 KB |
Output is correct |
37 |
Correct |
16 ms |
29524 KB |
Output is correct |
38 |
Correct |
16 ms |
29524 KB |
Output is correct |
39 |
Correct |
16 ms |
29776 KB |
Output is correct |
40 |
Correct |
15 ms |
29660 KB |
Output is correct |
41 |
Correct |
15 ms |
29672 KB |
Output is correct |
42 |
Correct |
15 ms |
29656 KB |
Output is correct |
43 |
Correct |
15 ms |
29660 KB |
Output is correct |
44 |
Correct |
17 ms |
29660 KB |
Output is correct |
45 |
Correct |
17 ms |
29660 KB |
Output is correct |
46 |
Correct |
17 ms |
29660 KB |
Output is correct |
47 |
Correct |
15 ms |
29660 KB |
Output is correct |
48 |
Correct |
127 ms |
50344 KB |
Output is correct |
49 |
Correct |
126 ms |
50468 KB |
Output is correct |
50 |
Correct |
130 ms |
50536 KB |
Output is correct |
51 |
Correct |
112 ms |
50300 KB |
Output is correct |
52 |
Correct |
107 ms |
48776 KB |
Output is correct |
53 |
Correct |
120 ms |
49604 KB |
Output is correct |
54 |
Correct |
119 ms |
48532 KB |
Output is correct |
55 |
Correct |
115 ms |
48328 KB |
Output is correct |
56 |
Correct |
113 ms |
48168 KB |
Output is correct |
57 |
Execution timed out |
2549 ms |
81356 KB |
Time limit exceeded |
58 |
Halted |
0 ms |
0 KB |
- |