oj.uz

Submission #411876

# Submission time Handle Problem Language Result Execution time Memory
411876 2021-05-26T07:44:42 Z 조영욱(#7630) Pastiri (COI20_pastiri) C++17
0 / 100
 1000 ms 580 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);
    }
    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]=max(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 (v[now]==v[now-1]+1) {
            v.push_back(v[now]);
            now--;
        }
        else if (v[now]==v[now-2]+1) {
            v.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:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=2;i<v.size();i++) {
      |                 ~^~~~~~~~~
pastiri.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 452 KB Output is correct
2 Execution timed out 1058 ms 428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 580 KB Time limit exceeded
2 Halted 0 ms 0 KB -