oj.uz

Submission #362815

# Submission time Handle Problem Language Result Execution time Memory
362815 2021-02-04T12:45:10 Z denkendoemeer Rope (JOI17_rope) C++14
0 / 100
 16 ms 23788 KB 
#include<bits/stdc++.h>
using namespace std;
int v[1000005],cost[1000005],ind[1000005];
vector<int>g[1000005];
int cmp(int a,int b)
{
    return cost[a]<cost[b];
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d",&v[i]);
        v[i]--;
        g[v[i]].push_back(i);
        cost[v[i]]--;
    }
    for(i=0;i<m;i++)
        ind[i]=i;
    sort(ind,ind+m,cmp);
    int cul;
    for(cul=0;cul<m;cul++){
        int ans=n-(int)g[cul].size();
        for(i=0;i<2;i++){
            int cnt=0;
            for(auto it:g[cul]){
                if (it<n-1 && (it+1)%2!=i){
                    cost[v[it+1]]++;
                    cnt++;
                }
                if (it>0 && it%2!=i){
                    cost[v[it-1]]++;
                    cnt++;
                }
            }
            cnt=min(cnt+2,m);
            int num=n;
            for(i=0;i<cnt;i++){
                if (ind[i]==cul)
                    continue;
                num=min(num,cost[ind[i]]);
            }
            ans=min(ans,n-(int)g[cul].size()+num);
            for(auto it:g[cul]){
                if (it<n-1 && (it+1)%2!=i)
                    cost[v[it+1]]--;
                if (it>0 && it%2!=i)
                    cost[v[it-1]]--;
            }
        }
        printf("%d\n",ans);
    }
return 0;
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
rope.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -