oj.uz

Submission #537445

# Submission time Handle Problem Language Result Execution time Memory
537445 2022-03-15T06:14:53 Z 79brue Rope (JOI17_rope) C++14
100 / 100
 1402 ms 135388 KB 
#include <bits/stdc++.h>
#define part opp

using namespace std;

typedef long long ll;

int n, k;
int arr[1000002];
int cnt[1000002];
int ans[1000002];
vector<int> occ[1000002];
int opp[1000002];

int onlyOne[1000002];
int both[1000002];
int freq[1000002];
int freqCnt[10000002], freqMax;

void add(int x){
    freqCnt[freq[x]]--; freqCnt[freq[x]+1]++;
    if(freqMax < freq[x]+1) freqMax = freq[x]+1;
    freq[x]++;
}

void del(int x){
    freqCnt[freq[x]]--; freqCnt[freq[x]-1]++;
    if(freqMax == freq[x] && freqCnt[freq[x]] == 0) freqMax--;
    freq[x]--;
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
        cnt[arr[i]]++;
        occ[arr[i]].push_back(i);
    }
    for(int i=1; i<=k; i++) ans[i] = n - cnt[i];

    for(int d=0; d<2; d++){ /// d가 시작점
        memset(onlyOne, 0, sizeof(onlyOne));
        memset(both, 0, sizeof(both));
        memset(freq, 0, sizeof(freq));
        memset(freqCnt, 0, sizeof(freqCnt));

        bool zeroNo = d;
        bool lastNo = (n%2 != d);

        for(int i=0; i<n; i++){
            opp[i] = (i%2 == d) ? i+1 : i-1;
        }

        for(int i=d; i+1<n; i+=2){
            freq[arr[i]]++, freq[arr[i+1]]++;
            if(arr[i] != arr[i+1]){
                onlyOne[arr[i]]++;
                onlyOne[arr[i+1]]++;
            }
            else both[arr[i]]++;
        }
        if(zeroNo) freq[arr[0]]++;
        if(lastNo) freq[arr[n-1]]++;
        freqMax = *max_element(freq+1, freq+k+1);
        for(int i=1; i<=k; i++) freqCnt[freq[i]]++;

        for(int i=1; i<=k; i++){
            int ret = onlyOne[i];
            int rest = n - cnt[i] - onlyOne[i];
            for(int x: occ[i]){
                if(part[x]<0 || part[x]>=n) del(i);
                else if(arr[part[x]] == i) del(i);
                else{
                    del(i);
                    del(arr[part[x]]);
                }
            }

            rest -= freqMax;
            ans[i] = min(ans[i], ret + rest);

            for(int x: occ[i]){
                if(part[x]<0 || part[x]>=n) add(i);
                else if(arr[part[x]] == i) add(i);
                else{
                    add(i);
                    add(arr[part[x]]);
                }
            }
        }
    }

    for(int i=1; i<=k; i++) printf("%d\n", ans[i]);
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 74624 KB Output is correct
2 Correct 43 ms 74676 KB Output is correct
3 Correct 50 ms 74608 KB Output is correct
4 Correct 41 ms 74572 KB Output is correct
5 Correct 41 ms 74604 KB Output is correct
6 Correct 41 ms 74580 KB Output is correct
7 Correct 42 ms 74684 KB Output is correct
8 Correct 51 ms 74672 KB Output is correct
9 Correct 42 ms 74628 KB Output is correct
10 Correct 43 ms 74592 KB Output is correct
11 Correct 46 ms 74588 KB Output is correct
12 Correct 42 ms 74676 KB Output is correct
13 Correct 40 ms 74612 KB Output is correct
14 Correct 40 ms 74656 KB Output is correct
15 Correct 43 ms 74572 KB Output is correct
16 Correct 48 ms 74620 KB Output is correct
17 Correct 47 ms 74688 KB Output is correct
18 Correct 46 ms 74620 KB Output is correct
19 Correct 41 ms 74672 KB Output is correct
20 Correct 42 ms 74648 KB Output is correct
21 Correct 42 ms 74676 KB Output is correct
22 Correct 43 ms 74572 KB Output is correct
23 Correct 43 ms 74572 KB Output is correct
24 Correct 39 ms 74676 KB Output is correct
25 Correct 40 ms 74692 KB Output is correct
26 Correct 40 ms 74700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 74624 KB Output is correct
2 Correct 43 ms 74676 KB Output is correct
3 Correct 50 ms 74608 KB Output is correct
4 Correct 41 ms 74572 KB Output is correct
5 Correct 41 ms 74604 KB Output is correct
6 Correct 41 ms 74580 KB Output is correct
7 Correct 42 ms 74684 KB Output is correct
8 Correct 51 ms 74672 KB Output is correct
9 Correct 42 ms 74628 KB Output is correct
10 Correct 43 ms 74592 KB Output is correct
11 Correct 46 ms 74588 KB Output is correct
12 Correct 42 ms 74676 KB Output is correct
13 Correct 40 ms 74612 KB Output is correct
14 Correct 40 ms 74656 KB Output is correct
15 Correct 43 ms 74572 KB Output is correct
16 Correct 48 ms 74620 KB Output is correct
17 Correct 47 ms 74688 KB Output is correct
18 Correct 46 ms 74620 KB Output is correct
19 Correct 41 ms 74672 KB Output is correct
20 Correct 42 ms 74648 KB Output is correct
21 Correct 42 ms 74676 KB Output is correct
22 Correct 43 ms 74572 KB Output is correct
23 Correct 43 ms 74572 KB Output is correct
24 Correct 39 ms 74676 KB Output is correct
25 Correct 40 ms 74692 KB Output is correct
26 Correct 40 ms 74700 KB Output is correct
27 Correct 53 ms 76244 KB Output is correct
28 Correct 57 ms 76224 KB Output is correct
29 Correct 58 ms 76244 KB Output is correct
30 Correct 55 ms 76236 KB Output is correct
31 Correct 53 ms 76236 KB Output is correct
32 Correct 56 ms 76272 KB Output is correct
33 Correct 61 ms 76288 KB Output is correct
34 Correct 64 ms 76308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 74624 KB Output is correct
2 Correct 43 ms 74676 KB Output is correct
3 Correct 50 ms 74608 KB Output is correct
4 Correct 41 ms 74572 KB Output is correct
5 Correct 41 ms 74604 KB Output is correct
6 Correct 41 ms 74580 KB Output is correct
7 Correct 42 ms 74684 KB Output is correct
8 Correct 51 ms 74672 KB Output is correct
9 Correct 42 ms 74628 KB Output is correct
10 Correct 43 ms 74592 KB Output is correct
11 Correct 46 ms 74588 KB Output is correct
12 Correct 42 ms 74676 KB Output is correct
13 Correct 40 ms 74612 KB Output is correct
14 Correct 40 ms 74656 KB Output is correct
15 Correct 43 ms 74572 KB Output is correct
16 Correct 48 ms 74620 KB Output is correct
17 Correct 47 ms 74688 KB Output is correct
18 Correct 46 ms 74620 KB Output is correct
19 Correct 41 ms 74672 KB Output is correct
20 Correct 42 ms 74648 KB Output is correct
21 Correct 42 ms 74676 KB Output is correct
22 Correct 43 ms 74572 KB Output is correct
23 Correct 43 ms 74572 KB Output is correct
24 Correct 39 ms 74676 KB Output is correct
25 Correct 40 ms 74692 KB Output is correct
26 Correct 40 ms 74700 KB Output is correct
27 Correct 53 ms 76244 KB Output is correct
28 Correct 57 ms 76224 KB Output is correct
29 Correct 58 ms 76244 KB Output is correct
30 Correct 55 ms 76236 KB Output is correct
31 Correct 53 ms 76236 KB Output is correct
32 Correct 56 ms 76272 KB Output is correct
33 Correct 61 ms 76288 KB Output is correct
34 Correct 64 ms 76308 KB Output is correct
35 Correct 58 ms 76364 KB Output is correct
36 Correct 60 ms 76432 KB Output is correct
37 Correct 61 ms 76304 KB Output is correct
38 Correct 59 ms 76364 KB Output is correct
39 Correct 67 ms 76344 KB Output is correct
40 Correct 67 ms 76436 KB Output is correct
41 Correct 58 ms 76440 KB Output is correct
42 Correct 55 ms 76372 KB Output is correct
43 Correct 56 ms 76400 KB Output is correct
44 Correct 61 ms 76492 KB Output is correct
45 Correct 70 ms 76396 KB Output is correct
46 Correct 57 ms 76492 KB Output is correct
47 Correct 56 ms 76412 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 74624 KB Output is correct
2 Correct 43 ms 74676 KB Output is correct
3 Correct 50 ms 74608 KB Output is correct
4 Correct 41 ms 74572 KB Output is correct
5 Correct 41 ms 74604 KB Output is correct
6 Correct 41 ms 74580 KB Output is correct
7 Correct 42 ms 74684 KB Output is correct
8 Correct 51 ms 74672 KB Output is correct
9 Correct 42 ms 74628 KB Output is correct
10 Correct 43 ms 74592 KB Output is correct
11 Correct 46 ms 74588 KB Output is correct
12 Correct 42 ms 74676 KB Output is correct
13 Correct 40 ms 74612 KB Output is correct
14 Correct 40 ms 74656 KB Output is correct
15 Correct 43 ms 74572 KB Output is correct
16 Correct 48 ms 74620 KB Output is correct
17 Correct 47 ms 74688 KB Output is correct
18 Correct 46 ms 74620 KB Output is correct
19 Correct 41 ms 74672 KB Output is correct
20 Correct 42 ms 74648 KB Output is correct
21 Correct 42 ms 74676 KB Output is correct
22 Correct 43 ms 74572 KB Output is correct
23 Correct 43 ms 74572 KB Output is correct
24 Correct 39 ms 74676 KB Output is correct
25 Correct 40 ms 74692 KB Output is correct
26 Correct 40 ms 74700 KB Output is correct
27 Correct 53 ms 76244 KB Output is correct
28 Correct 57 ms 76224 KB Output is correct
29 Correct 58 ms 76244 KB Output is correct
30 Correct 55 ms 76236 KB Output is correct
31 Correct 53 ms 76236 KB Output is correct
32 Correct 56 ms 76272 KB Output is correct
33 Correct 61 ms 76288 KB Output is correct
34 Correct 64 ms 76308 KB Output is correct
35 Correct 58 ms 76364 KB Output is correct
36 Correct 60 ms 76432 KB Output is correct
37 Correct 61 ms 76304 KB Output is correct
38 Correct 59 ms 76364 KB Output is correct
39 Correct 67 ms 76344 KB Output is correct
40 Correct 67 ms 76436 KB Output is correct
41 Correct 58 ms 76440 KB Output is correct
42 Correct 55 ms 76372 KB Output is correct
43 Correct 56 ms 76400 KB Output is correct
44 Correct 61 ms 76492 KB Output is correct
45 Correct 70 ms 76396 KB Output is correct
46 Correct 57 ms 76492 KB Output is correct
47 Correct 56 ms 76412 KB Output is correct
48 Correct 515 ms 93680 KB Output is correct
49 Correct 468 ms 93732 KB Output is correct
50 Correct 443 ms 93776 KB Output is correct
51 Correct 501 ms 93472 KB Output is correct
52 Correct 388 ms 92032 KB Output is correct
53 Correct 302 ms 92884 KB Output is correct
54 Correct 231 ms 91864 KB Output is correct
55 Correct 276 ms 91724 KB Output is correct
56 Correct 223 ms 91496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 74624 KB Output is correct
2 Correct 43 ms 74676 KB Output is correct
3 Correct 50 ms 74608 KB Output is correct
4 Correct 41 ms 74572 KB Output is correct
5 Correct 41 ms 74604 KB Output is correct
6 Correct 41 ms 74580 KB Output is correct
7 Correct 42 ms 74684 KB Output is correct
8 Correct 51 ms 74672 KB Output is correct
9 Correct 42 ms 74628 KB Output is correct
10 Correct 43 ms 74592 KB Output is correct
11 Correct 46 ms 74588 KB Output is correct
12 Correct 42 ms 74676 KB Output is correct
13 Correct 40 ms 74612 KB Output is correct
14 Correct 40 ms 74656 KB Output is correct
15 Correct 43 ms 74572 KB Output is correct
16 Correct 48 ms 74620 KB Output is correct
17 Correct 47 ms 74688 KB Output is correct
18 Correct 46 ms 74620 KB Output is correct
19 Correct 41 ms 74672 KB Output is correct
20 Correct 42 ms 74648 KB Output is correct
21 Correct 42 ms 74676 KB Output is correct
22 Correct 43 ms 74572 KB Output is correct
23 Correct 43 ms 74572 KB Output is correct
24 Correct 39 ms 74676 KB Output is correct
25 Correct 40 ms 74692 KB Output is correct
26 Correct 40 ms 74700 KB Output is correct
27 Correct 53 ms 76244 KB Output is correct
28 Correct 57 ms 76224 KB Output is correct
29 Correct 58 ms 76244 KB Output is correct
30 Correct 55 ms 76236 KB Output is correct
31 Correct 53 ms 76236 KB Output is correct
32 Correct 56 ms 76272 KB Output is correct
33 Correct 61 ms 76288 KB Output is correct
34 Correct 64 ms 76308 KB Output is correct
35 Correct 58 ms 76364 KB Output is correct
36 Correct 60 ms 76432 KB Output is correct
37 Correct 61 ms 76304 KB Output is correct
38 Correct 59 ms 76364 KB Output is correct
39 Correct 67 ms 76344 KB Output is correct
40 Correct 67 ms 76436 KB Output is correct
41 Correct 58 ms 76440 KB Output is correct
42 Correct 55 ms 76372 KB Output is correct
43 Correct 56 ms 76400 KB Output is correct
44 Correct 61 ms 76492 KB Output is correct
45 Correct 70 ms 76396 KB Output is correct
46 Correct 57 ms 76492 KB Output is correct
47 Correct 56 ms 76412 KB Output is correct
48 Correct 515 ms 93680 KB Output is correct
49 Correct 468 ms 93732 KB Output is correct
50 Correct 443 ms 93776 KB Output is correct
51 Correct 501 ms 93472 KB Output is correct
52 Correct 388 ms 92032 KB Output is correct
53 Correct 302 ms 92884 KB Output is correct
54 Correct 231 ms 91864 KB Output is correct
55 Correct 276 ms 91724 KB Output is correct
56 Correct 223 ms 91496 KB Output is correct
57 Correct 1402 ms 135388 KB Output is correct
58 Correct 1093 ms 116916 KB Output is correct
59 Correct 1103 ms 116700 KB Output is correct
60 Correct 1219 ms 121408 KB Output is correct
61 Correct 1277 ms 121440 KB Output is correct
62 Correct 600 ms 105876 KB Output is correct
63 Correct 810 ms 111184 KB Output is correct
64 Correct 665 ms 107980 KB Output is correct
65 Correct 406 ms 99472 KB Output is correct