답안 #83439 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83439	2018-11-07T15:22:54 Z	Bodo171	Rope (JOI17_rope)	C++14	100 / 100	1545 ms	121688 KB

rope

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=1000*1000+5;
vector<int> l[nmax],v[nmax];
int pr[nmax];
int comb[nmax];
int a[nmax],ap[nmax],ans[nmax];
int n,m,i,j,nr,pnt;
int check(int a,int b)
{
    return n-(ap[a]+ap[b]-comb[b]);
}
void solve(int st,int dr)
{
    for(i=1;i<=m;i++)
        v[i].clear();
    for(i=st;i<dr;i+=2)
        if(a[i]!=a[i+1])
        {
            v[a[i]].push_back(a[i+1]);
            v[a[i+1]].push_back(a[i]);
        }
    for(i=1;i<=m;i++)
    {
        for(j=0;j<v[i].size();j++)
            comb[v[i][j]]++;
        for(j=0;j<v[i].size();j++)
            ans[i]=min(check(i,v[i][j]),ans[i]);
        pnt=m;
        while(pnt>0&&(comb[pr[pnt]]||pr[pnt]==i))
            pnt--;
        if(pnt)
            ans[i]=min(check(i,pr[pnt]),ans[i]);
        for(j=0;j<v[i].size();j++)
            comb[v[i][j]]--;
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++)
        ans[i]=n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        ap[a[i]]++;
        ans[a[i]]--;
    }
    nr=0;
    for(i=1;i<=m;i++)
        l[ap[i]].push_back(i);
    for(i=1;i<=n;i++)
        for(j=0;j<l[i].size();j++)
          pr[++nr]=l[i][j];
    solve(1,n-n%2);
    solve(2,n-1+n%2);
    for(i=1;i<=m;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Compilation message

rope.cpp: In function 'void solve(int, int)':
rope.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp: In function 'int main()':
rope.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<l[i].size();j++)
                 ~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	47352 KB	Output is correct
2	Correct	47 ms	47352 KB	Output is correct
3	Correct	45 ms	47384 KB	Output is correct
4	Correct	44 ms	47432 KB	Output is correct
5	Correct	45 ms	47480 KB	Output is correct
6	Correct	48 ms	47480 KB	Output is correct
7	Correct	45 ms	47528 KB	Output is correct
8	Correct	46 ms	47540 KB	Output is correct
9	Correct	48 ms	47588 KB	Output is correct
10	Correct	46 ms	47588 KB	Output is correct
11	Correct	46 ms	47588 KB	Output is correct
12	Correct	45 ms	47684 KB	Output is correct
13	Correct	47 ms	47684 KB	Output is correct
14	Correct	46 ms	47696 KB	Output is correct
15	Correct	51 ms	47696 KB	Output is correct
16	Correct	44 ms	47696 KB	Output is correct
17	Correct	46 ms	47696 KB	Output is correct
18	Correct	45 ms	47696 KB	Output is correct
19	Correct	48 ms	47696 KB	Output is correct
20	Correct	47 ms	47696 KB	Output is correct
21	Correct	44 ms	47696 KB	Output is correct
22	Correct	50 ms	47696 KB	Output is correct
23	Correct	48 ms	47696 KB	Output is correct
24	Correct	43 ms	47696 KB	Output is correct
25	Correct	45 ms	47696 KB	Output is correct
26	Correct	44 ms	47728 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	47352 KB	Output is correct
2	Correct	47 ms	47352 KB	Output is correct
3	Correct	45 ms	47384 KB	Output is correct
4	Correct	44 ms	47432 KB	Output is correct
5	Correct	45 ms	47480 KB	Output is correct
6	Correct	48 ms	47480 KB	Output is correct
7	Correct	45 ms	47528 KB	Output is correct
8	Correct	46 ms	47540 KB	Output is correct
9	Correct	48 ms	47588 KB	Output is correct
10	Correct	46 ms	47588 KB	Output is correct
11	Correct	46 ms	47588 KB	Output is correct
12	Correct	45 ms	47684 KB	Output is correct
13	Correct	47 ms	47684 KB	Output is correct
14	Correct	46 ms	47696 KB	Output is correct
15	Correct	51 ms	47696 KB	Output is correct
16	Correct	44 ms	47696 KB	Output is correct
17	Correct	46 ms	47696 KB	Output is correct
18	Correct	45 ms	47696 KB	Output is correct
19	Correct	48 ms	47696 KB	Output is correct
20	Correct	47 ms	47696 KB	Output is correct
21	Correct	44 ms	47696 KB	Output is correct
22	Correct	50 ms	47696 KB	Output is correct
23	Correct	48 ms	47696 KB	Output is correct
24	Correct	43 ms	47696 KB	Output is correct
25	Correct	45 ms	47696 KB	Output is correct
26	Correct	44 ms	47728 KB	Output is correct
27	Correct	59 ms	48728 KB	Output is correct
28	Correct	58 ms	48884 KB	Output is correct
29	Correct	57 ms	49120 KB	Output is correct
30	Correct	56 ms	49120 KB	Output is correct
31	Correct	58 ms	49276 KB	Output is correct
32	Correct	55 ms	49276 KB	Output is correct
33	Correct	55 ms	49276 KB	Output is correct
34	Correct	57 ms	49276 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	47352 KB	Output is correct
2	Correct	47 ms	47352 KB	Output is correct
3	Correct	45 ms	47384 KB	Output is correct
4	Correct	44 ms	47432 KB	Output is correct
5	Correct	45 ms	47480 KB	Output is correct
6	Correct	48 ms	47480 KB	Output is correct
7	Correct	45 ms	47528 KB	Output is correct
8	Correct	46 ms	47540 KB	Output is correct
9	Correct	48 ms	47588 KB	Output is correct
10	Correct	46 ms	47588 KB	Output is correct
11	Correct	46 ms	47588 KB	Output is correct
12	Correct	45 ms	47684 KB	Output is correct
13	Correct	47 ms	47684 KB	Output is correct
14	Correct	46 ms	47696 KB	Output is correct
15	Correct	51 ms	47696 KB	Output is correct
16	Correct	44 ms	47696 KB	Output is correct
17	Correct	46 ms	47696 KB	Output is correct
18	Correct	45 ms	47696 KB	Output is correct
19	Correct	48 ms	47696 KB	Output is correct
20	Correct	47 ms	47696 KB	Output is correct
21	Correct	44 ms	47696 KB	Output is correct
22	Correct	50 ms	47696 KB	Output is correct
23	Correct	48 ms	47696 KB	Output is correct
24	Correct	43 ms	47696 KB	Output is correct
25	Correct	45 ms	47696 KB	Output is correct
26	Correct	44 ms	47728 KB	Output is correct
27	Correct	59 ms	48728 KB	Output is correct
28	Correct	58 ms	48884 KB	Output is correct
29	Correct	57 ms	49120 KB	Output is correct
30	Correct	56 ms	49120 KB	Output is correct
31	Correct	58 ms	49276 KB	Output is correct
32	Correct	55 ms	49276 KB	Output is correct
33	Correct	55 ms	49276 KB	Output is correct
34	Correct	57 ms	49276 KB	Output is correct
35	Correct	69 ms	49276 KB	Output is correct
36	Correct	57 ms	49276 KB	Output is correct
37	Correct	60 ms	49276 KB	Output is correct
38	Correct	60 ms	49276 KB	Output is correct
39	Correct	57 ms	49276 KB	Output is correct
40	Correct	61 ms	49276 KB	Output is correct
41	Correct	58 ms	49276 KB	Output is correct
42	Correct	65 ms	49276 KB	Output is correct
43	Correct	60 ms	49276 KB	Output is correct
44	Correct	58 ms	49276 KB	Output is correct
45	Correct	58 ms	49276 KB	Output is correct
46	Correct	62 ms	49276 KB	Output is correct
47	Correct	128 ms	49288 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	47352 KB	Output is correct
2	Correct	47 ms	47352 KB	Output is correct
3	Correct	45 ms	47384 KB	Output is correct
4	Correct	44 ms	47432 KB	Output is correct
5	Correct	45 ms	47480 KB	Output is correct
6	Correct	48 ms	47480 KB	Output is correct
7	Correct	45 ms	47528 KB	Output is correct
8	Correct	46 ms	47540 KB	Output is correct
9	Correct	48 ms	47588 KB	Output is correct
10	Correct	46 ms	47588 KB	Output is correct
11	Correct	46 ms	47588 KB	Output is correct
12	Correct	45 ms	47684 KB	Output is correct
13	Correct	47 ms	47684 KB	Output is correct
14	Correct	46 ms	47696 KB	Output is correct
15	Correct	51 ms	47696 KB	Output is correct
16	Correct	44 ms	47696 KB	Output is correct
17	Correct	46 ms	47696 KB	Output is correct
18	Correct	45 ms	47696 KB	Output is correct
19	Correct	48 ms	47696 KB	Output is correct
20	Correct	47 ms	47696 KB	Output is correct
21	Correct	44 ms	47696 KB	Output is correct
22	Correct	50 ms	47696 KB	Output is correct
23	Correct	48 ms	47696 KB	Output is correct
24	Correct	43 ms	47696 KB	Output is correct
25	Correct	45 ms	47696 KB	Output is correct
26	Correct	44 ms	47728 KB	Output is correct
27	Correct	59 ms	48728 KB	Output is correct
28	Correct	58 ms	48884 KB	Output is correct
29	Correct	57 ms	49120 KB	Output is correct
30	Correct	56 ms	49120 KB	Output is correct
31	Correct	58 ms	49276 KB	Output is correct
32	Correct	55 ms	49276 KB	Output is correct
33	Correct	55 ms	49276 KB	Output is correct
34	Correct	57 ms	49276 KB	Output is correct
35	Correct	69 ms	49276 KB	Output is correct
36	Correct	57 ms	49276 KB	Output is correct
37	Correct	60 ms	49276 KB	Output is correct
38	Correct	60 ms	49276 KB	Output is correct
39	Correct	57 ms	49276 KB	Output is correct
40	Correct	61 ms	49276 KB	Output is correct
41	Correct	58 ms	49276 KB	Output is correct
42	Correct	65 ms	49276 KB	Output is correct
43	Correct	60 ms	49276 KB	Output is correct
44	Correct	58 ms	49276 KB	Output is correct
45	Correct	58 ms	49276 KB	Output is correct
46	Correct	62 ms	49276 KB	Output is correct
47	Correct	128 ms	49288 KB	Output is correct
48	Correct	222 ms	58888 KB	Output is correct
49	Correct	215 ms	59000 KB	Output is correct
50	Correct	208 ms	59000 KB	Output is correct
51	Correct	204 ms	59000 KB	Output is correct
52	Correct	217 ms	59000 KB	Output is correct
53	Correct	197 ms	59000 KB	Output is correct
54	Correct	196 ms	59000 KB	Output is correct
55	Correct	220 ms	59000 KB	Output is correct
56	Correct	179 ms	59000 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	47352 KB	Output is correct
2	Correct	47 ms	47352 KB	Output is correct
3	Correct	45 ms	47384 KB	Output is correct
4	Correct	44 ms	47432 KB	Output is correct
5	Correct	45 ms	47480 KB	Output is correct
6	Correct	48 ms	47480 KB	Output is correct
7	Correct	45 ms	47528 KB	Output is correct
8	Correct	46 ms	47540 KB	Output is correct
9	Correct	48 ms	47588 KB	Output is correct
10	Correct	46 ms	47588 KB	Output is correct
11	Correct	46 ms	47588 KB	Output is correct
12	Correct	45 ms	47684 KB	Output is correct
13	Correct	47 ms	47684 KB	Output is correct
14	Correct	46 ms	47696 KB	Output is correct
15	Correct	51 ms	47696 KB	Output is correct
16	Correct	44 ms	47696 KB	Output is correct
17	Correct	46 ms	47696 KB	Output is correct
18	Correct	45 ms	47696 KB	Output is correct
19	Correct	48 ms	47696 KB	Output is correct
20	Correct	47 ms	47696 KB	Output is correct
21	Correct	44 ms	47696 KB	Output is correct
22	Correct	50 ms	47696 KB	Output is correct
23	Correct	48 ms	47696 KB	Output is correct
24	Correct	43 ms	47696 KB	Output is correct
25	Correct	45 ms	47696 KB	Output is correct
26	Correct	44 ms	47728 KB	Output is correct
27	Correct	59 ms	48728 KB	Output is correct
28	Correct	58 ms	48884 KB	Output is correct
29	Correct	57 ms	49120 KB	Output is correct
30	Correct	56 ms	49120 KB	Output is correct
31	Correct	58 ms	49276 KB	Output is correct
32	Correct	55 ms	49276 KB	Output is correct
33	Correct	55 ms	49276 KB	Output is correct
34	Correct	57 ms	49276 KB	Output is correct
35	Correct	69 ms	49276 KB	Output is correct
36	Correct	57 ms	49276 KB	Output is correct
37	Correct	60 ms	49276 KB	Output is correct
38	Correct	60 ms	49276 KB	Output is correct
39	Correct	57 ms	49276 KB	Output is correct
40	Correct	61 ms	49276 KB	Output is correct
41	Correct	58 ms	49276 KB	Output is correct
42	Correct	65 ms	49276 KB	Output is correct
43	Correct	60 ms	49276 KB	Output is correct
44	Correct	58 ms	49276 KB	Output is correct
45	Correct	58 ms	49276 KB	Output is correct
46	Correct	62 ms	49276 KB	Output is correct
47	Correct	128 ms	49288 KB	Output is correct
48	Correct	222 ms	58888 KB	Output is correct
49	Correct	215 ms	59000 KB	Output is correct
50	Correct	208 ms	59000 KB	Output is correct
51	Correct	204 ms	59000 KB	Output is correct
52	Correct	217 ms	59000 KB	Output is correct
53	Correct	197 ms	59000 KB	Output is correct
54	Correct	196 ms	59000 KB	Output is correct
55	Correct	220 ms	59000 KB	Output is correct
56	Correct	179 ms	59000 KB	Output is correct
57	Correct	1545 ms	109968 KB	Output is correct
58	Correct	1212 ms	109968 KB	Output is correct
59	Correct	1217 ms	109968 KB	Output is correct
60	Correct	1364 ms	112792 KB	Output is correct
61	Correct	1377 ms	119544 KB	Output is correct
62	Correct	500 ms	119544 KB	Output is correct
63	Correct	644 ms	119544 KB	Output is correct
64	Correct	543 ms	121688 KB	Output is correct
65	Correct	299 ms	121688 KB	Output is correct

답안 #83439

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 30.0 / 30.0

Subtask #3 10.0 / 10.0

Subtask #4 25.0 / 25.0

Subtask #5 20.0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
30.0 / 30.0

Subtask #3
10.0 / 10.0

Subtask #4
25.0 / 25.0

Subtask #5
20.0 / 20.0