답안 #892070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892070	2023-12-24T18:16:18 Z	Mihailo	즐거운 행로 (APIO20_fun)	C++14	100 / 100	172 ms	26224 KB

#include <bits/stdc++.h>
#include "fun.h"
#define mp make_pair
using namespace std;

long long c, d[200000], l[4], k[200000], x, p[200000], M, m, ctr;
priority_queue<pair<long long, long long> > q[4];

vector<int> createFunTour(int n, int Q) {
    c=1;
    for(int i=2; i<=n; i++) {
        if(attractionsBehind(c-1, i-1)>=n/2) c=i;
    }
    x=1;
    for(int i=1; i<=n; i++) {
        if(i!=c) d[i]=hoursRequired(c-1, i-1);
        if(d[i]==1) {l[x]=i;k[i]=x;x++;}
    }
    for(int i=1; i<=n; i++) {
        if(k[i]==0&&i!=c) {
            if(hoursRequired(i-1, l[1]-1)<d[i]) k[i]=1;
            else if(hoursRequired(i-1, l[2]-1)<d[i]) k[i]=2;
            else k[i]=3;
        }
    }
    for(int i=1; i<=n; i++) {
        q[k[i]].push(mp(d[i], i));
    }
    x=0;
    ctr=1;
    while(2*max(max(q[1].size(), q[2].size()), q[3].size())<q[1].size()+q[2].size()+q[3].size()) {
        m=0;
        for(int i=1; i<=3; i++) {
            if(i!=x) {
                if(m<q[i].top().first) {
                    m=q[i].top().first;
                    M=i;
                }
            }
        }
        x=M;
        p[ctr]=q[x].top().second;
        ctr++;
        q[x].pop();
    }
    for(int i=1; i<=3; i++) {
        if(q[i].size()==max(max(q[1].size(), q[2].size()), q[3].size())) M=i;
    }
    for(int i=1; i<=3; i++) {
        if(x!=i&&m!=i&&(q[i].empty()?-1:q[i].top().first)==max(max((q[1].empty()?-1:q[1].top().first), (q[2].empty()?-1:q[2].top().first)), (q[3].empty()?-1:q[3].top().first))) {
            if(q[i].empty()) {
                continue;
            }
            p[ctr]=q[i].top().second;
            ctr++;
            q[i].pop();
            x=i;
        }
    }
    if(M!=x) {
        p[ctr]=q[M].top().second;
        ctr++;
        q[M].pop();
        x=M;
    }
    while(2*max(max(q[1].size(), q[2].size()), q[3].size())>0) {
        m=0;
        if(x==M)
            for(int i=1; i<=3; i++) {
                if(i!=M) {
                    if(m<(q[i].empty()?-1:q[i].top().first)) {
                        m=(q[i].empty()?-1:q[i].top().first);
                        x=i;
                    }
                }
            }
        else x=M;
        p[ctr]=q[x].top().second;
        ctr++;
        q[x].pop();
    }
    p[ctr]=c;
    vector<int> v;
    for(int i=1; i<=ctr; i++) v.push_back(p[i]-1);
    return v;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4536 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4540 KB	Output is correct
18	Correct	1 ms	4444 KB	Output is correct
19	Correct	1 ms	4528 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4536 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4540 KB	Output is correct
18	Correct	1 ms	4444 KB	Output is correct
19	Correct	1 ms	4528 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct
21	Correct	1 ms	4444 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	4536 KB	Output is correct
25	Correct	1 ms	4696 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4444 KB	Output is correct
29	Correct	1 ms	4444 KB	Output is correct
30	Correct	1 ms	4444 KB	Output is correct
31	Correct	1 ms	4444 KB	Output is correct
32	Correct	1 ms	4444 KB	Output is correct
33	Correct	1 ms	4444 KB	Output is correct
34	Correct	2 ms	4440 KB	Output is correct
35	Correct	1 ms	4444 KB	Output is correct
36	Correct	1 ms	4444 KB	Output is correct
37	Correct	1 ms	4444 KB	Output is correct
38	Correct	1 ms	4444 KB	Output is correct
39	Correct	1 ms	4444 KB	Output is correct
40	Correct	1 ms	4444 KB	Output is correct
41	Correct	1 ms	4540 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4440 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4536 KB	Output is correct
13	Correct	1 ms	4696 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4444 KB	Output is correct
18	Correct	96 ms	21520 KB	Output is correct
19	Correct	2 ms	4440 KB	Output is correct
20	Correct	2 ms	4696 KB	Output is correct
21	Correct	3 ms	4956 KB	Output is correct
22	Correct	5 ms	5608 KB	Output is correct
23	Correct	9 ms	6748 KB	Output is correct
24	Correct	13 ms	7640 KB	Output is correct
25	Correct	54 ms	14184 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4536 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	7 ms	5988 KB	Output is correct
15	Correct	103 ms	20136 KB	Output is correct
16	Correct	107 ms	19888 KB	Output is correct
17	Correct	19 ms	8148 KB	Output is correct
18	Correct	44 ms	11552 KB	Output is correct
19	Correct	73 ms	16796 KB	Output is correct
20	Correct	4 ms	5208 KB	Output is correct

Subtask #5
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4536 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4540 KB	Output is correct
18	Correct	1 ms	4444 KB	Output is correct
19	Correct	1 ms	4528 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct
21	Correct	1 ms	4444 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	4536 KB	Output is correct
25	Correct	1 ms	4696 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4444 KB	Output is correct
29	Correct	1 ms	4444 KB	Output is correct
30	Correct	1 ms	4444 KB	Output is correct
31	Correct	1 ms	4444 KB	Output is correct
32	Correct	1 ms	4444 KB	Output is correct
33	Correct	1 ms	4444 KB	Output is correct
34	Correct	2 ms	4440 KB	Output is correct
35	Correct	1 ms	4444 KB	Output is correct
36	Correct	1 ms	4444 KB	Output is correct
37	Correct	1 ms	4444 KB	Output is correct
38	Correct	1 ms	4444 KB	Output is correct
39	Correct	1 ms	4444 KB	Output is correct
40	Correct	1 ms	4444 KB	Output is correct
41	Correct	1 ms	4540 KB	Output is correct
42	Correct	1 ms	4444 KB	Output is correct
43	Correct	1 ms	4444 KB	Output is correct
44	Correct	96 ms	21520 KB	Output is correct
45	Correct	2 ms	4440 KB	Output is correct
46	Correct	2 ms	4696 KB	Output is correct
47	Correct	3 ms	4956 KB	Output is correct
48	Correct	5 ms	5608 KB	Output is correct
49	Correct	9 ms	6748 KB	Output is correct
50	Correct	13 ms	7640 KB	Output is correct
51	Correct	54 ms	14184 KB	Output is correct
52	Correct	1 ms	4444 KB	Output is correct
53	Correct	7 ms	5988 KB	Output is correct
54	Correct	103 ms	20136 KB	Output is correct
55	Correct	107 ms	19888 KB	Output is correct
56	Correct	19 ms	8148 KB	Output is correct
57	Correct	44 ms	11552 KB	Output is correct
58	Correct	73 ms	16796 KB	Output is correct
59	Correct	4 ms	5208 KB	Output is correct
60	Correct	133 ms	21188 KB	Output is correct
61	Correct	144 ms	23836 KB	Output is correct
62	Correct	121 ms	21700 KB	Output is correct
63	Correct	134 ms	25540 KB	Output is correct
64	Correct	128 ms	25176 KB	Output is correct
65	Correct	124 ms	21444 KB	Output is correct
66	Correct	150 ms	23412 KB	Output is correct
67	Correct	133 ms	25284 KB	Output is correct
68	Correct	133 ms	24772 KB	Output is correct
69	Correct	165 ms	25800 KB	Output is correct
70	Correct	114 ms	21192 KB	Output is correct
71	Correct	126 ms	25284 KB	Output is correct
72	Correct	149 ms	23748 KB	Output is correct
73	Correct	141 ms	24260 KB	Output is correct
74	Correct	172 ms	26224 KB	Output is correct
75	Correct	128 ms	21192 KB	Output is correct
76	Correct	129 ms	25092 KB	Output is correct
77	Correct	142 ms	25096 KB	Output is correct
78	Correct	144 ms	24836 KB	Output is correct
79	Correct	154 ms	25768 KB	Output is correct
80	Correct	167 ms	26032 KB	Output is correct
81	Correct	121 ms	21192 KB	Output is correct
82	Correct	128 ms	21448 KB	Output is correct
83	Correct	144 ms	21336 KB	Output is correct
84	Correct	50 ms	11760 KB	Output is correct

답안 #892070

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 19.0 / 19.0

Subtask #5 34.0 / 34.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
19.0 / 19.0

Subtask #5
34.0 / 34.0