oj.uz

Submission #411886

# Submission time Handle Problem Language Result Execution time Memory
411886 2021-05-26T07:50:03 Z 조영욱(#7630) Pastiri (COI20_pastiri) C++17
8 / 100
 235 ms 6276 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int dp[500000];

int main(void) {
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<n;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
    }
    for(int i=0;i<k;i++) {
        int x;
        scanf("%d",&x);
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    dp[0]=1;
    dp[1]=2;
    if (v.size()>1&&(v[1]-v[0])%2==0) {
        dp[1]=1;
    }
    for(int i=2;i<v.size();i++) {
        dp[i]=dp[i-1]+1;
        if ((v[i]-v[i-1])%2==0) {
            dp[i]=min(dp[i],dp[i-2]+1);
        }
    }
    int now=v.size()-1;
    printf("%d\n",dp[now]);
    vector<int> ret;
    while (1) {
        if (now==0) {
            ret.push_back(v[now]);
            break;
        }
        if (now==1) {
            if ((v[1]-v[0])%2==0) {
                ret.push_back((v[0]+v[1])/2);
            }
            else {
                ret.push_back(v[1]);
                ret.push_back(v[0]);
            }
            break;
        }
        if (dp[now]==dp[now-1]+1) {
            ret.push_back(v[now]);
            now--;
        }
        else if (dp[now]==dp[now-2]+1) {
            ret.push_back((v[now-1]+v[now])/2);
            now-=2;
        }
    }
    reverse(ret.begin(),ret.end());
    for(int i=0;i<ret.size();i++) {
        printf("%d ",ret[i]);
    }
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=2;i<v.size();i++) {
      |                 ~^~~~~~~~~
pastiri.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<ret.size();i++) {
      |                 ~^~~~~~~~~~~
pastiri.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
pastiri.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
pastiri.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 276 KB Output is correct
2 Correct 106 ms 288 KB Output is correct
3 Correct 132 ms 556 KB Output is correct
4 Correct 235 ms 6276 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 204 KB Sheep 3030 not protected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB Sheep 128 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 400 KB Sheep 54 not protected
2 Halted 0 ms 0 KB -