답안 #83429 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83429	2018-11-07T14:42:22 Z	Bodo171	Rope (JOI17_rope)	C++14	0 / 100	54 ms	47680 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],simple[nmax],duble[nmax],comb[nmax],ans[nmax];
int n,m,i,j,nr,pnt;
int check(int a,int b)
{
    return n-(simple[a]+simple[b]+2*duble[a]+2*duble[b]-comb[b]);
}
void solve(int st,int dr)
{
    if(st>dr)
        return;
    for(i=1;i<=m;i++)
        v[i].clear(),simple[i]=duble[i]=0;
    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]);
        }
        if(a[i]==a[i+1]) duble[a[i]]++;
        else simple[a[i]]++,simple[a[i+1]]++;
    }
    if(st>1) simple[a[st-1]]++;
    if(dr<n) simple[a[dr+1]]++;
    nr=0;
    for(i=1;i<=m;i++)
        l[2*duble[i]+simple[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];
        //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:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<l[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
rope.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~

Subtask #1
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	47352 KB	Output is correct
2	Correct	44 ms	47476 KB	Output is correct
3	Correct	44 ms	47476 KB	Output is correct
4	Correct	45 ms	47504 KB	Output is correct
5	Correct	45 ms	47504 KB	Output is correct
6	Correct	45 ms	47532 KB	Output is correct
7	Correct	44 ms	47536 KB	Output is correct
8	Correct	45 ms	47540 KB	Output is correct
9	Correct	47 ms	47616 KB	Output is correct
10	Correct	44 ms	47624 KB	Output is correct
11	Correct	50 ms	47624 KB	Output is correct
12	Correct	44 ms	47624 KB	Output is correct
13	Correct	44 ms	47652 KB	Output is correct
14	Correct	45 ms	47652 KB	Output is correct
15	Correct	45 ms	47660 KB	Output is correct
16	Correct	45 ms	47664 KB	Output is correct
17	Correct	45 ms	47668 KB	Output is correct
18	Correct	46 ms	47672 KB	Output is correct
19	Correct	47 ms	47676 KB	Output is correct
20	Correct	46 ms	47680 KB	Output is correct
21	Incorrect	45 ms	47680 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	47352 KB	Output is correct
2	Correct	44 ms	47476 KB	Output is correct
3	Correct	44 ms	47476 KB	Output is correct
4	Correct	45 ms	47504 KB	Output is correct
5	Correct	45 ms	47504 KB	Output is correct
6	Correct	45 ms	47532 KB	Output is correct
7	Correct	44 ms	47536 KB	Output is correct
8	Correct	45 ms	47540 KB	Output is correct
9	Correct	47 ms	47616 KB	Output is correct
10	Correct	44 ms	47624 KB	Output is correct
11	Correct	50 ms	47624 KB	Output is correct
12	Correct	44 ms	47624 KB	Output is correct
13	Correct	44 ms	47652 KB	Output is correct
14	Correct	45 ms	47652 KB	Output is correct
15	Correct	45 ms	47660 KB	Output is correct
16	Correct	45 ms	47664 KB	Output is correct
17	Correct	45 ms	47668 KB	Output is correct
18	Correct	46 ms	47672 KB	Output is correct
19	Correct	47 ms	47676 KB	Output is correct
20	Correct	46 ms	47680 KB	Output is correct
21	Incorrect	45 ms	47680 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	47352 KB	Output is correct
2	Correct	44 ms	47476 KB	Output is correct
3	Correct	44 ms	47476 KB	Output is correct
4	Correct	45 ms	47504 KB	Output is correct
5	Correct	45 ms	47504 KB	Output is correct
6	Correct	45 ms	47532 KB	Output is correct
7	Correct	44 ms	47536 KB	Output is correct
8	Correct	45 ms	47540 KB	Output is correct
9	Correct	47 ms	47616 KB	Output is correct
10	Correct	44 ms	47624 KB	Output is correct
11	Correct	50 ms	47624 KB	Output is correct
12	Correct	44 ms	47624 KB	Output is correct
13	Correct	44 ms	47652 KB	Output is correct
14	Correct	45 ms	47652 KB	Output is correct
15	Correct	45 ms	47660 KB	Output is correct
16	Correct	45 ms	47664 KB	Output is correct
17	Correct	45 ms	47668 KB	Output is correct
18	Correct	46 ms	47672 KB	Output is correct
19	Correct	47 ms	47676 KB	Output is correct
20	Correct	46 ms	47680 KB	Output is correct
21	Incorrect	45 ms	47680 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	47352 KB	Output is correct
2	Correct	44 ms	47476 KB	Output is correct
3	Correct	44 ms	47476 KB	Output is correct
4	Correct	45 ms	47504 KB	Output is correct
5	Correct	45 ms	47504 KB	Output is correct
6	Correct	45 ms	47532 KB	Output is correct
7	Correct	44 ms	47536 KB	Output is correct
8	Correct	45 ms	47540 KB	Output is correct
9	Correct	47 ms	47616 KB	Output is correct
10	Correct	44 ms	47624 KB	Output is correct
11	Correct	50 ms	47624 KB	Output is correct
12	Correct	44 ms	47624 KB	Output is correct
13	Correct	44 ms	47652 KB	Output is correct
14	Correct	45 ms	47652 KB	Output is correct
15	Correct	45 ms	47660 KB	Output is correct
16	Correct	45 ms	47664 KB	Output is correct
17	Correct	45 ms	47668 KB	Output is correct
18	Correct	46 ms	47672 KB	Output is correct
19	Correct	47 ms	47676 KB	Output is correct
20	Correct	46 ms	47680 KB	Output is correct
21	Incorrect	45 ms	47680 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	47352 KB	Output is correct
2	Correct	44 ms	47476 KB	Output is correct
3	Correct	44 ms	47476 KB	Output is correct
4	Correct	45 ms	47504 KB	Output is correct
5	Correct	45 ms	47504 KB	Output is correct
6	Correct	45 ms	47532 KB	Output is correct
7	Correct	44 ms	47536 KB	Output is correct
8	Correct	45 ms	47540 KB	Output is correct
9	Correct	47 ms	47616 KB	Output is correct
10	Correct	44 ms	47624 KB	Output is correct
11	Correct	50 ms	47624 KB	Output is correct
12	Correct	44 ms	47624 KB	Output is correct
13	Correct	44 ms	47652 KB	Output is correct
14	Correct	45 ms	47652 KB	Output is correct
15	Correct	45 ms	47660 KB	Output is correct
16	Correct	45 ms	47664 KB	Output is correct
17	Correct	45 ms	47668 KB	Output is correct
18	Correct	46 ms	47672 KB	Output is correct
19	Correct	47 ms	47676 KB	Output is correct
20	Correct	46 ms	47680 KB	Output is correct
21	Incorrect	45 ms	47680 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #83429

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