oj.uz

Submission #83429

# Submission time Handle Problem Language Result Execution time Memory
83429 2018-11-07T14:42:22 Z Bodo171 Rope (JOI17_rope) C++14
0 / 100
 54 ms 47680 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -