Submission #837297

#	Time	Username	Problem	Language	Result	Execution time	Memory
837297		unnick	Rope (JOI17_rope)	C++14	45 / 100	2540 ms	980 KiB

rope

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> colors(n);
    vector<int> color_counts(m, 0);
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        colors[i] = tmp-1;
        color_counts[tmp-1]++;
    }
    if (m == 1) {
        cout << "0\n";
        return 0;
    }
    vector<int> answers(m, 2000000000);
    for (int q = 0; q < 2; q++) {
        // cout << "q=" << q << "\n";
        // vector<int> col_ngb;
        // for (int i = q; i < n-1; q+=2) {
        //     int a = colors[i];
        //     int b = colors[i+1];
        //     if (a==b) continue;
        //     col_ngb[a]++;
        //     col_ngb[b]++;
        // }
        for (int c = 0; c < m; c++) {
            // cout << " c=" << c << "\n";
            int dom = -1;
            int domc = 0;
            for (int d = 0; d < m; d++) {
                if (d==c) continue;
                // cout << "  d=" << d << "\n";
                int count = n&1?q?(colors[0]==d):(colors[n-1]==d):q?((colors[0]==d)+(colors[n-1]==d)):0;
                for (int i = q; i < n-1; i+=2) {
                    int a = colors[i];
                    int b = colors[i+1];
                    if (a==c || b==c) continue;
                    if (a == d) count++;
                    if (b == d) count++;
                }
                // cout << "   " << count << "\n";
                if(count > domc) {
                    domc = count;
                    dom = d;
                }
            }
            answers[c] = min(answers[c], n-color_counts[c]-domc);
            // cout << n - color_counts[c] - domc << "\n";
        }
    }
    for (int a : answers) {
        cout << a << "\n";
    }
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:34:17: warning: variable 'dom' set but not used [-Wunused-but-set-variable]
   34 |             int dom = -1;
      |                 ^~~

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