Submission #758126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
758126	2023-06-14T07:59:33 Z	PixelCat	Rope (JOI17_rope)	C++14	0 / 100	7 ms	8160 KB

rope

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

void chmin(int &x, int a) {
    x = min(x, a);
}
void chmax(int &x, int a) {
    x = max(x, a);
}

const int MAXN = 1000010;

int ans[MAXN];
int cnt1[MAXN];

void solve(int n, int m, vector<pii> v2, vector<int> v1) {
    for(auto &i:v2) {
        if(i.F > i.S) swap(i.F, i.S);
    }  // i.F <= i.S

    memset(cnt1, 0, sizeof(cnt1));
    map<pii, int> cnt2;
    for(auto &i:v2) {
        cnt1[i.F]++;
        cnt1[i.S]++;
        cnt2[i]++;
    }

    For(c1, 1, m) {
        For(c2, c1 + 1, m) {
            int cost = n - cnt1[c1] - cnt1[c2] + cnt2[pii(c1, c2)];
            for(auto &i:v1) {
                cost -= max(i == c1, i == c2);
            }
            chmin(ans[c1], cost);
            chmin(ans[c2], cost);
        }
        int cost = n - cnt1[c1];
        chmin(ans[c1], cost);
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for(auto &i:a) cin >> i;

    For(i, 1, m) {
        ans[i] = INF;
    }

    if(n % 2) {
        For(_, 0, 1) {
            vector<pii> v2;
            for(int i = 1; i < n; i += 2) {
                v2.eb(pii(a[i - 1], a[i]));
            }
            solve(n, m, v2, { a.back() });
            reverse(all(a));
        }
    } else {
        vector<pii> v2;
        for(int i = 1; i < n; i += 2) {
            v2.eb(pii(a[i - 1], a[i]));
        }
        solve(n, m, v2, {});

        v2.clear();
        for(int i = 2; i < n; i += 2) {
            v2.eb(pii(a[i - 1], a[i]));
        }
        solve(n, m, v2, { a.front(), a.back() });
    }

    For(i, 1, m) cout << ans[i] << "\n";
    return 0;
}

Subtask #1
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8148 KB	Output is correct
2	Correct	5 ms	8148 KB	Output is correct
3	Correct	4 ms	8148 KB	Output is correct
4	Correct	5 ms	8148 KB	Output is correct
5	Correct	4 ms	8148 KB	Output is correct
6	Correct	4 ms	8148 KB	Output is correct
7	Correct	5 ms	8148 KB	Output is correct
8	Correct	5 ms	8148 KB	Output is correct
9	Correct	6 ms	8156 KB	Output is correct
10	Correct	7 ms	8136 KB	Output is correct
11	Correct	5 ms	8136 KB	Output is correct
12	Correct	5 ms	8132 KB	Output is correct
13	Correct	5 ms	8148 KB	Output is correct
14	Correct	5 ms	8148 KB	Output is correct
15	Correct	5 ms	8160 KB	Output is correct
16	Correct	5 ms	8148 KB	Output is correct
17	Correct	4 ms	8148 KB	Output is correct
18	Correct	5 ms	8148 KB	Output is correct
19	Correct	5 ms	8148 KB	Output is correct
20	Correct	5 ms	8148 KB	Output is correct
21	Correct	5 ms	8148 KB	Output is correct
22	Correct	5 ms	8148 KB	Output is correct
23	Correct	5 ms	8132 KB	Output is correct
24	Correct	4 ms	8148 KB	Output is correct
25	Correct	5 ms	8148 KB	Output is correct
26	Incorrect	5 ms	8148 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8148 KB	Output is correct
2	Correct	5 ms	8148 KB	Output is correct
3	Correct	4 ms	8148 KB	Output is correct
4	Correct	5 ms	8148 KB	Output is correct
5	Correct	4 ms	8148 KB	Output is correct
6	Correct	4 ms	8148 KB	Output is correct
7	Correct	5 ms	8148 KB	Output is correct
8	Correct	5 ms	8148 KB	Output is correct
9	Correct	6 ms	8156 KB	Output is correct
10	Correct	7 ms	8136 KB	Output is correct
11	Correct	5 ms	8136 KB	Output is correct
12	Correct	5 ms	8132 KB	Output is correct
13	Correct	5 ms	8148 KB	Output is correct
14	Correct	5 ms	8148 KB	Output is correct
15	Correct	5 ms	8160 KB	Output is correct
16	Correct	5 ms	8148 KB	Output is correct
17	Correct	4 ms	8148 KB	Output is correct
18	Correct	5 ms	8148 KB	Output is correct
19	Correct	5 ms	8148 KB	Output is correct
20	Correct	5 ms	8148 KB	Output is correct
21	Correct	5 ms	8148 KB	Output is correct
22	Correct	5 ms	8148 KB	Output is correct
23	Correct	5 ms	8132 KB	Output is correct
24	Correct	4 ms	8148 KB	Output is correct
25	Correct	5 ms	8148 KB	Output is correct
26	Incorrect	5 ms	8148 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8148 KB	Output is correct
2	Correct	5 ms	8148 KB	Output is correct
3	Correct	4 ms	8148 KB	Output is correct
4	Correct	5 ms	8148 KB	Output is correct
5	Correct	4 ms	8148 KB	Output is correct
6	Correct	4 ms	8148 KB	Output is correct
7	Correct	5 ms	8148 KB	Output is correct
8	Correct	5 ms	8148 KB	Output is correct
9	Correct	6 ms	8156 KB	Output is correct
10	Correct	7 ms	8136 KB	Output is correct
11	Correct	5 ms	8136 KB	Output is correct
12	Correct	5 ms	8132 KB	Output is correct
13	Correct	5 ms	8148 KB	Output is correct
14	Correct	5 ms	8148 KB	Output is correct
15	Correct	5 ms	8160 KB	Output is correct
16	Correct	5 ms	8148 KB	Output is correct
17	Correct	4 ms	8148 KB	Output is correct
18	Correct	5 ms	8148 KB	Output is correct
19	Correct	5 ms	8148 KB	Output is correct
20	Correct	5 ms	8148 KB	Output is correct
21	Correct	5 ms	8148 KB	Output is correct
22	Correct	5 ms	8148 KB	Output is correct
23	Correct	5 ms	8132 KB	Output is correct
24	Correct	4 ms	8148 KB	Output is correct
25	Correct	5 ms	8148 KB	Output is correct
26	Incorrect	5 ms	8148 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8148 KB	Output is correct
2	Correct	5 ms	8148 KB	Output is correct
3	Correct	4 ms	8148 KB	Output is correct
4	Correct	5 ms	8148 KB	Output is correct
5	Correct	4 ms	8148 KB	Output is correct
6	Correct	4 ms	8148 KB	Output is correct
7	Correct	5 ms	8148 KB	Output is correct
8	Correct	5 ms	8148 KB	Output is correct
9	Correct	6 ms	8156 KB	Output is correct
10	Correct	7 ms	8136 KB	Output is correct
11	Correct	5 ms	8136 KB	Output is correct
12	Correct	5 ms	8132 KB	Output is correct
13	Correct	5 ms	8148 KB	Output is correct
14	Correct	5 ms	8148 KB	Output is correct
15	Correct	5 ms	8160 KB	Output is correct
16	Correct	5 ms	8148 KB	Output is correct
17	Correct	4 ms	8148 KB	Output is correct
18	Correct	5 ms	8148 KB	Output is correct
19	Correct	5 ms	8148 KB	Output is correct
20	Correct	5 ms	8148 KB	Output is correct
21	Correct	5 ms	8148 KB	Output is correct
22	Correct	5 ms	8148 KB	Output is correct
23	Correct	5 ms	8132 KB	Output is correct
24	Correct	4 ms	8148 KB	Output is correct
25	Correct	5 ms	8148 KB	Output is correct
26	Incorrect	5 ms	8148 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8148 KB	Output is correct
2	Correct	5 ms	8148 KB	Output is correct
3	Correct	4 ms	8148 KB	Output is correct
4	Correct	5 ms	8148 KB	Output is correct
5	Correct	4 ms	8148 KB	Output is correct
6	Correct	4 ms	8148 KB	Output is correct
7	Correct	5 ms	8148 KB	Output is correct
8	Correct	5 ms	8148 KB	Output is correct
9	Correct	6 ms	8156 KB	Output is correct
10	Correct	7 ms	8136 KB	Output is correct
11	Correct	5 ms	8136 KB	Output is correct
12	Correct	5 ms	8132 KB	Output is correct
13	Correct	5 ms	8148 KB	Output is correct
14	Correct	5 ms	8148 KB	Output is correct
15	Correct	5 ms	8160 KB	Output is correct
16	Correct	5 ms	8148 KB	Output is correct
17	Correct	4 ms	8148 KB	Output is correct
18	Correct	5 ms	8148 KB	Output is correct
19	Correct	5 ms	8148 KB	Output is correct
20	Correct	5 ms	8148 KB	Output is correct
21	Correct	5 ms	8148 KB	Output is correct
22	Correct	5 ms	8148 KB	Output is correct
23	Correct	5 ms	8132 KB	Output is correct
24	Correct	4 ms	8148 KB	Output is correct
25	Correct	5 ms	8148 KB	Output is correct
26	Incorrect	5 ms	8148 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Submission #758126

Compilation message

Subtask #1 0 / 15.0

Subtask #2 0 / 30.0

Subtask #3 0 / 10.0

Subtask #4 0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
0 / 15.0

Subtask #2
0 / 30.0

Subtask #3
0 / 10.0

Subtask #4
0 / 25.0

Subtask #5
0 / 20.0