Submission #600579

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600579	2022-07-21T05:32:48 Z	이동현(#8470)	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	242 ms	340 KB

arranging_tickets

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> a(m, vector<int>(3));
    for(int i = 0; i < m; ++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        --a[i][0], --a[i][1];
        int len = (a[i][1] + n - a[i][0]) % n;
        if(len * 2 > n){
            swap(a[i][0], a[i][1]);
        }
    }
    sort(a.begin(), a.end());
    int ans = (int)1e18;
    for(int i = 0; i < (1 << m); ++i){
        vector<int> sum(n);
        for(int k = 0; k < m; ++k){
            if(1 & (i >> k)) swap(a[k][0], a[k][1]);
            if(a[k][0] < a[k][1]){
                ++sum[a[k][0]];
                --sum[a[k][1]];
            }
            else{
                ++sum[a[k][0]];
                ++sum[0];
                --sum[a[k][1]];
            }
            if(1 & (i >> k)) swap(a[k][0], a[k][1]);
        }
        int mx = 0;
        for(int k = 0; k < n; ++k){
            if(k) sum[k] += sum[k - 1];
            mx = max(mx, sum[k]);
        }
        ans = min(ans, mx);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	300 KB	Output is correct
2	Correct	222 ms	292 KB	Output is correct
3	Correct	220 ms	296 KB	Output is correct
4	Correct	212 ms	292 KB	Output is correct
5	Correct	225 ms	296 KB	Output is correct
6	Correct	222 ms	296 KB	Output is correct
7	Correct	219 ms	300 KB	Output is correct
8	Correct	228 ms	300 KB	Output is correct
9	Correct	222 ms	292 KB	Output is correct
10	Correct	215 ms	296 KB	Output is correct
11	Correct	242 ms	308 KB	Output is correct
12	Correct	215 ms	292 KB	Output is correct
13	Correct	221 ms	296 KB	Output is correct
14	Correct	224 ms	296 KB	Output is correct
15	Correct	220 ms	300 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	300 KB	Output is correct
2	Correct	222 ms	292 KB	Output is correct
3	Correct	220 ms	296 KB	Output is correct
4	Correct	212 ms	292 KB	Output is correct
5	Correct	225 ms	296 KB	Output is correct
6	Correct	222 ms	296 KB	Output is correct
7	Correct	219 ms	300 KB	Output is correct
8	Correct	228 ms	300 KB	Output is correct
9	Correct	222 ms	292 KB	Output is correct
10	Correct	215 ms	296 KB	Output is correct
11	Correct	242 ms	308 KB	Output is correct
12	Correct	215 ms	292 KB	Output is correct
13	Correct	221 ms	296 KB	Output is correct
14	Correct	224 ms	296 KB	Output is correct
15	Correct	220 ms	300 KB	Output is correct
16	Incorrect	12 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	300 KB	Output is correct
2	Correct	222 ms	292 KB	Output is correct
3	Correct	220 ms	296 KB	Output is correct
4	Correct	212 ms	292 KB	Output is correct
5	Correct	225 ms	296 KB	Output is correct
6	Correct	222 ms	296 KB	Output is correct
7	Correct	219 ms	300 KB	Output is correct
8	Correct	228 ms	300 KB	Output is correct
9	Correct	222 ms	292 KB	Output is correct
10	Correct	215 ms	296 KB	Output is correct
11	Correct	242 ms	308 KB	Output is correct
12	Correct	215 ms	292 KB	Output is correct
13	Correct	221 ms	296 KB	Output is correct
14	Correct	224 ms	296 KB	Output is correct
15	Correct	220 ms	300 KB	Output is correct
16	Incorrect	12 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	300 KB	Output is correct
2	Correct	222 ms	292 KB	Output is correct
3	Correct	220 ms	296 KB	Output is correct
4	Correct	212 ms	292 KB	Output is correct
5	Correct	225 ms	296 KB	Output is correct
6	Correct	222 ms	296 KB	Output is correct
7	Correct	219 ms	300 KB	Output is correct
8	Correct	228 ms	300 KB	Output is correct
9	Correct	222 ms	292 KB	Output is correct
10	Correct	215 ms	296 KB	Output is correct
11	Correct	242 ms	308 KB	Output is correct
12	Correct	215 ms	292 KB	Output is correct
13	Correct	221 ms	296 KB	Output is correct
14	Correct	224 ms	296 KB	Output is correct
15	Correct	220 ms	300 KB	Output is correct
16	Incorrect	12 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	300 KB	Output is correct
2	Correct	222 ms	292 KB	Output is correct
3	Correct	220 ms	296 KB	Output is correct
4	Correct	212 ms	292 KB	Output is correct
5	Correct	225 ms	296 KB	Output is correct
6	Correct	222 ms	296 KB	Output is correct
7	Correct	219 ms	300 KB	Output is correct
8	Correct	228 ms	300 KB	Output is correct
9	Correct	222 ms	292 KB	Output is correct
10	Correct	215 ms	296 KB	Output is correct
11	Correct	242 ms	308 KB	Output is correct
12	Correct	215 ms	292 KB	Output is correct
13	Correct	221 ms	296 KB	Output is correct
14	Correct	224 ms	296 KB	Output is correct
15	Correct	220 ms	300 KB	Output is correct
16	Incorrect	12 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-