Submission #291921

#	Time	Username	Problem	Language	Result	Execution time	Memory
291921		anonymous	Rope (JOI17_rope)	C++14	45 / 100	2569 ms	1152 KiB

rope

#include <iostream>
#define MAXN 1000005
#define MAXM 15
using namespace std;
int N, M, C[MAXN], Ans[MAXM];

int main() {
    //freopen("ropein.txt","r",stdin);
    scanf("%d %d",&N,&M);
    for (int i=1; i<=M; i++) {
        Ans[i] = N;
    }
    for (int i=1; i<=N; i++) {
        scanf("%d",&C[i]);
        Ans[C[i]] -= 1;
    }

    for (int i=1; i<=M; i++) {
        for (int j=i+1; j <= M; j++) {
            //case 1: A[1] = A[2] ...
            int ans1 = 0, ans2 = 0;
            for (int k=1; k<N; k+=2) {
                if (C[k] != i && C[k] != j && C[k+1] != i && C[k+1] != j) {ans1+=2;}
                else if (C[k] != C[k+1]) {ans1 += 1;}
            }
            if (N%2 && C[N] != i && C[N] != j) {ans1++;}
            //case 2: A[2] = A[3] ...
            for (int k=2; k<N; k+=2) {
                if (C[k] != i && C[k] != j && C[k+1] != i && C[k+1] != j) {ans2+=2;}
                else if (C[k] != C[k+1]) {ans2 += 1;}
            }
            if (C[1] != i && C[1] != j) {ans2++;}
            if (N%2 == 0 && C[N] != i && C[N] != j) {ans2++;}
            Ans[i] = min(Ans[i], min(ans1,ans2));
            Ans[j] = min(Ans[j], min(ans1,ans2));
            //printf("%d %d %d %d\n",i,j,ans1,ans2);
        }
    }

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

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20