Submission #766468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
766468	2023-06-25T16:56:48 Z	Sogol	Arranging Tickets (JOI17_arranging_tickets)	C++17	65 / 100	6000 ms	36144 KB

arranging_tickets

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

typedef long long ll;
 
#define pb       push_back
#define Sz(x)    int((x).size())
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
 
const int maxn  =  1e6   + 10;
const int maxa  =  2e9   +  5;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;
const double eps = 1e-9;

int a[maxn], b[maxn], c[maxn], ps[maxn], n, m;
vector <int> vc[maxn];
multiset <int> s;

int cal(int ind){
    s.cl();
    fill(ps, ps + n, 0);
    for (int i = 0; i < n; i ++) vc[i].cl();
    for (int i = 0; i < m; i ++) a[i] = (a[i] - ind + n) % n, b[i] = (b[i] - ind + n) % n;
    for (int i = 0; i < m; i ++){
        int x = min(a[i], b[i]), y = max(a[i], b[i]);
        ps[x] ++;
        ps[y] --;
        vc[x].pb(y);
    }
    int ans = 0;
    for (int i = 0; i < n; i ++){
        while (!s.empty() && *s.begin() == i) s.erase(s.begin());
        for (int x : vc[i]) s.insert(x);
        if(i) ps[i] += ps[i - 1];
        while (ps[i] > 0){
            int t = *s.rbegin();
            s.erase(s.find(t));
            ps[i] -= 2;
            ps[t] += 2;
            ans ++;
        }
    }
    for (int i = 0; i < m; i ++) a[i] = (a[i] + ind) % n, b[i] = (b[i] + ind) % n;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i ++) cin >> a[i] >> b[i] >> c[i], a[i] --, b[i] --;
    int ans = mod;
    for (int i = 0; i < n; i ++) ans = min(ans, cal(i));
    cout << ans << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	11 ms	23836 KB	Output is correct
3	Correct	11 ms	23780 KB	Output is correct
4	Correct	11 ms	23764 KB	Output is correct
5	Correct	10 ms	23816 KB	Output is correct
6	Correct	11 ms	23820 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23808 KB	Output is correct
9	Correct	12 ms	23816 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23804 KB	Output is correct
12	Correct	11 ms	23764 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23728 KB	Output is correct

Subtask #2
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	11 ms	23836 KB	Output is correct
3	Correct	11 ms	23780 KB	Output is correct
4	Correct	11 ms	23764 KB	Output is correct
5	Correct	10 ms	23816 KB	Output is correct
6	Correct	11 ms	23820 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23808 KB	Output is correct
9	Correct	12 ms	23816 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23804 KB	Output is correct
12	Correct	11 ms	23764 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23728 KB	Output is correct
16	Correct	21 ms	23816 KB	Output is correct
17	Correct	21 ms	23808 KB	Output is correct
18	Correct	21 ms	23868 KB	Output is correct
19	Correct	21 ms	23764 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	21 ms	23764 KB	Output is correct
22	Correct	21 ms	23864 KB	Output is correct
23	Correct	22 ms	23812 KB	Output is correct
24	Correct	23 ms	23852 KB	Output is correct
25	Correct	21 ms	23808 KB	Output is correct
26	Correct	21 ms	23812 KB	Output is correct
27	Correct	21 ms	23896 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	11 ms	23836 KB	Output is correct
3	Correct	11 ms	23780 KB	Output is correct
4	Correct	11 ms	23764 KB	Output is correct
5	Correct	10 ms	23816 KB	Output is correct
6	Correct	11 ms	23820 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23808 KB	Output is correct
9	Correct	12 ms	23816 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23804 KB	Output is correct
12	Correct	11 ms	23764 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23728 KB	Output is correct
16	Correct	21 ms	23816 KB	Output is correct
17	Correct	21 ms	23808 KB	Output is correct
18	Correct	21 ms	23868 KB	Output is correct
19	Correct	21 ms	23764 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	21 ms	23764 KB	Output is correct
22	Correct	21 ms	23864 KB	Output is correct
23	Correct	22 ms	23812 KB	Output is correct
24	Correct	23 ms	23852 KB	Output is correct
25	Correct	21 ms	23808 KB	Output is correct
26	Correct	21 ms	23812 KB	Output is correct
27	Correct	21 ms	23896 KB	Output is correct
28	Correct	1198 ms	24128 KB	Output is correct
29	Correct	1208 ms	24096 KB	Output is correct
30	Correct	1188 ms	24128 KB	Output is correct
31	Correct	1173 ms	24256 KB	Output is correct
32	Correct	1157 ms	24480 KB	Output is correct
33	Correct	1283 ms	26876 KB	Output is correct
34	Correct	1231 ms	26840 KB	Output is correct
35	Correct	1289 ms	29860 KB	Output is correct
36	Correct	1274 ms	26916 KB	Output is correct
37	Correct	853 ms	24020 KB	Output is correct
38	Correct	629 ms	24000 KB	Output is correct
39	Correct	805 ms	24108 KB	Output is correct

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	11 ms	23836 KB	Output is correct
3	Correct	11 ms	23780 KB	Output is correct
4	Correct	11 ms	23764 KB	Output is correct
5	Correct	10 ms	23816 KB	Output is correct
6	Correct	11 ms	23820 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23808 KB	Output is correct
9	Correct	12 ms	23816 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23804 KB	Output is correct
12	Correct	11 ms	23764 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23728 KB	Output is correct
16	Correct	21 ms	23816 KB	Output is correct
17	Correct	21 ms	23808 KB	Output is correct
18	Correct	21 ms	23868 KB	Output is correct
19	Correct	21 ms	23764 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	21 ms	23764 KB	Output is correct
22	Correct	21 ms	23864 KB	Output is correct
23	Correct	22 ms	23812 KB	Output is correct
24	Correct	23 ms	23852 KB	Output is correct
25	Correct	21 ms	23808 KB	Output is correct
26	Correct	21 ms	23812 KB	Output is correct
27	Correct	21 ms	23896 KB	Output is correct
28	Correct	1198 ms	24128 KB	Output is correct
29	Correct	1208 ms	24096 KB	Output is correct
30	Correct	1188 ms	24128 KB	Output is correct
31	Correct	1173 ms	24256 KB	Output is correct
32	Correct	1157 ms	24480 KB	Output is correct
33	Correct	1283 ms	26876 KB	Output is correct
34	Correct	1231 ms	26840 KB	Output is correct
35	Correct	1289 ms	29860 KB	Output is correct
36	Correct	1274 ms	26916 KB	Output is correct
37	Correct	853 ms	24020 KB	Output is correct
38	Correct	629 ms	24000 KB	Output is correct
39	Correct	805 ms	24108 KB	Output is correct
40	Execution timed out	6016 ms	36144 KB	Time limit exceeded
41	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	11 ms	23836 KB	Output is correct
3	Correct	11 ms	23780 KB	Output is correct
4	Correct	11 ms	23764 KB	Output is correct
5	Correct	10 ms	23816 KB	Output is correct
6	Correct	11 ms	23820 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23808 KB	Output is correct
9	Correct	12 ms	23816 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23804 KB	Output is correct
12	Correct	11 ms	23764 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23728 KB	Output is correct
16	Correct	21 ms	23816 KB	Output is correct
17	Correct	21 ms	23808 KB	Output is correct
18	Correct	21 ms	23868 KB	Output is correct
19	Correct	21 ms	23764 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	21 ms	23764 KB	Output is correct
22	Correct	21 ms	23864 KB	Output is correct
23	Correct	22 ms	23812 KB	Output is correct
24	Correct	23 ms	23852 KB	Output is correct
25	Correct	21 ms	23808 KB	Output is correct
26	Correct	21 ms	23812 KB	Output is correct
27	Correct	21 ms	23896 KB	Output is correct
28	Correct	1198 ms	24128 KB	Output is correct
29	Correct	1208 ms	24096 KB	Output is correct
30	Correct	1188 ms	24128 KB	Output is correct
31	Correct	1173 ms	24256 KB	Output is correct
32	Correct	1157 ms	24480 KB	Output is correct
33	Correct	1283 ms	26876 KB	Output is correct
34	Correct	1231 ms	26840 KB	Output is correct
35	Correct	1289 ms	29860 KB	Output is correct
36	Correct	1274 ms	26916 KB	Output is correct
37	Correct	853 ms	24020 KB	Output is correct
38	Correct	629 ms	24000 KB	Output is correct
39	Correct	805 ms	24108 KB	Output is correct
40	Execution timed out	6016 ms	36144 KB	Time limit exceeded
41	Halted	0 ms	0 KB	-

Submission #766468

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 35.0 / 35.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 20.0

Subtask #5 0 / 15.0

Subtask #1
10.0 / 10.0

Subtask #2
35.0 / 35.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 20.0

Subtask #5
0 / 15.0