Submission #537445

#	Time	Username	Problem	Language	Result	Execution time	Memory
537445		79brue	Rope (JOI17_rope)	C++14	100 / 100	1402 ms	135388 KiB

rope

#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 (stderr)

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 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20