Submission #83432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83432	2018-11-07T14:45:44 Z	Bodo171	Rope (JOI17_rope)	C++14	0 / 100	51 ms	47740 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 a[nmax],ap[nmax],comb[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)
{
    if(st>dr)
        return;
    for(i=1;i<=m;i++)
        v[i].clear();
    for(i=1;i<=n;i++)
        l[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]);
        }
    }
    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];
    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]);
        if(i!=a[1])
            ans[i]=min(check(i,a[1]),ans[i]);
        if(i!=a[n])
            ans[i]=min(check(i,a[n]),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);
    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]]--;
    }
    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:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<l[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~

Subtask #1
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47352 KB	Output is correct
2	Correct	45 ms	47364 KB	Output is correct
3	Correct	44 ms	47408 KB	Output is correct
4	Correct	44 ms	47612 KB	Output is correct
5	Correct	43 ms	47612 KB	Output is correct
6	Correct	43 ms	47612 KB	Output is correct
7	Correct	46 ms	47612 KB	Output is correct
8	Correct	47 ms	47612 KB	Output is correct
9	Correct	44 ms	47612 KB	Output is correct
10	Correct	47 ms	47612 KB	Output is correct
11	Correct	47 ms	47612 KB	Output is correct
12	Correct	45 ms	47632 KB	Output is correct
13	Correct	45 ms	47632 KB	Output is correct
14	Correct	46 ms	47632 KB	Output is correct
15	Correct	44 ms	47632 KB	Output is correct
16	Correct	51 ms	47740 KB	Output is correct
17	Correct	46 ms	47740 KB	Output is correct
18	Correct	45 ms	47740 KB	Output is correct
19	Correct	45 ms	47740 KB	Output is correct
20	Correct	45 ms	47740 KB	Output is correct
21	Incorrect	45 ms	47740 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47352 KB	Output is correct
2	Correct	45 ms	47364 KB	Output is correct
3	Correct	44 ms	47408 KB	Output is correct
4	Correct	44 ms	47612 KB	Output is correct
5	Correct	43 ms	47612 KB	Output is correct
6	Correct	43 ms	47612 KB	Output is correct
7	Correct	46 ms	47612 KB	Output is correct
8	Correct	47 ms	47612 KB	Output is correct
9	Correct	44 ms	47612 KB	Output is correct
10	Correct	47 ms	47612 KB	Output is correct
11	Correct	47 ms	47612 KB	Output is correct
12	Correct	45 ms	47632 KB	Output is correct
13	Correct	45 ms	47632 KB	Output is correct
14	Correct	46 ms	47632 KB	Output is correct
15	Correct	44 ms	47632 KB	Output is correct
16	Correct	51 ms	47740 KB	Output is correct
17	Correct	46 ms	47740 KB	Output is correct
18	Correct	45 ms	47740 KB	Output is correct
19	Correct	45 ms	47740 KB	Output is correct
20	Correct	45 ms	47740 KB	Output is correct
21	Incorrect	45 ms	47740 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47352 KB	Output is correct
2	Correct	45 ms	47364 KB	Output is correct
3	Correct	44 ms	47408 KB	Output is correct
4	Correct	44 ms	47612 KB	Output is correct
5	Correct	43 ms	47612 KB	Output is correct
6	Correct	43 ms	47612 KB	Output is correct
7	Correct	46 ms	47612 KB	Output is correct
8	Correct	47 ms	47612 KB	Output is correct
9	Correct	44 ms	47612 KB	Output is correct
10	Correct	47 ms	47612 KB	Output is correct
11	Correct	47 ms	47612 KB	Output is correct
12	Correct	45 ms	47632 KB	Output is correct
13	Correct	45 ms	47632 KB	Output is correct
14	Correct	46 ms	47632 KB	Output is correct
15	Correct	44 ms	47632 KB	Output is correct
16	Correct	51 ms	47740 KB	Output is correct
17	Correct	46 ms	47740 KB	Output is correct
18	Correct	45 ms	47740 KB	Output is correct
19	Correct	45 ms	47740 KB	Output is correct
20	Correct	45 ms	47740 KB	Output is correct
21	Incorrect	45 ms	47740 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47352 KB	Output is correct
2	Correct	45 ms	47364 KB	Output is correct
3	Correct	44 ms	47408 KB	Output is correct
4	Correct	44 ms	47612 KB	Output is correct
5	Correct	43 ms	47612 KB	Output is correct
6	Correct	43 ms	47612 KB	Output is correct
7	Correct	46 ms	47612 KB	Output is correct
8	Correct	47 ms	47612 KB	Output is correct
9	Correct	44 ms	47612 KB	Output is correct
10	Correct	47 ms	47612 KB	Output is correct
11	Correct	47 ms	47612 KB	Output is correct
12	Correct	45 ms	47632 KB	Output is correct
13	Correct	45 ms	47632 KB	Output is correct
14	Correct	46 ms	47632 KB	Output is correct
15	Correct	44 ms	47632 KB	Output is correct
16	Correct	51 ms	47740 KB	Output is correct
17	Correct	46 ms	47740 KB	Output is correct
18	Correct	45 ms	47740 KB	Output is correct
19	Correct	45 ms	47740 KB	Output is correct
20	Correct	45 ms	47740 KB	Output is correct
21	Incorrect	45 ms	47740 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47352 KB	Output is correct
2	Correct	45 ms	47364 KB	Output is correct
3	Correct	44 ms	47408 KB	Output is correct
4	Correct	44 ms	47612 KB	Output is correct
5	Correct	43 ms	47612 KB	Output is correct
6	Correct	43 ms	47612 KB	Output is correct
7	Correct	46 ms	47612 KB	Output is correct
8	Correct	47 ms	47612 KB	Output is correct
9	Correct	44 ms	47612 KB	Output is correct
10	Correct	47 ms	47612 KB	Output is correct
11	Correct	47 ms	47612 KB	Output is correct
12	Correct	45 ms	47632 KB	Output is correct
13	Correct	45 ms	47632 KB	Output is correct
14	Correct	46 ms	47632 KB	Output is correct
15	Correct	44 ms	47632 KB	Output is correct
16	Correct	51 ms	47740 KB	Output is correct
17	Correct	46 ms	47740 KB	Output is correct
18	Correct	45 ms	47740 KB	Output is correct
19	Correct	45 ms	47740 KB	Output is correct
20	Correct	45 ms	47740 KB	Output is correct
21	Incorrect	45 ms	47740 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Submission #83432

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