oj.uz

Submission #417677

# Submission time Handle Problem Language Result Execution time Memory
417677 2021-06-04T06:24:34 Z 조영욱(#7641) Diamond Hands (innopolis2021_final_B) C++17
6 / 100
 2 ms 1996 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
long long d[200001];
long long p[200001];
int dp[200001][2];

int ans(int ind,int type) {
    if (ind==n) {
        return 0;
    }
    if (dp[ind][type]!=-1) {
        return dp[ind][type];
    }
    int ret=1e6;
    if (type==1&&p[ind+1]==p[ind]+d[ind+1]-d[ind]) {
        ret=min(ret,ans(ind+1,1));
    }
    if (type==0&&p[ind+1]==p[ind]-d[ind+1]+d[ind]) {
        ret=min(ret,ans(ind+1,0));
    }
    ret=min(ret,ans(ind+1,1-type)+1);
    return dp[ind][type]=ret;
}

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lld %lld",&d[i],&p[i]);
    }
    for(int i=1;i<=n;i++) {
        if (((d[i-1]+p[i-1])&1)!=((d[i]+p[i])&1)) {
            printf("-1");
            return 0;
        }
        if (abs(d[i]-d[i-1])<abs(p[i]-p[i-1])) {
            printf("-1");
            return 0;
        }
    }
    memset(dp,-1,sizeof(dp));
    printf("%d\n",min(ans(0,0),ans(0,1))+1);
    int now=min(ans(0,0),ans(0,1));
    int type;
    if (ans(0,0)<ans(0,1)) {
        type=0;
    }
    else {
        type=1;
    }
    int prev=0;
    for(int i=1;i<=n;i++) {
        if (ans(i,type)==now) {
            continue;
        }
        else {
            int t;
            if (type==0) {
                t=d[i-1]+(d[i]-d[i-1]-p[i]+p[i-1])/2;
            }
            else {
                t=d[i-1]+(d[i]-d[i-1]+p[i]-p[i-1])/2;
            }
            printf("%d",t-prev);
            printf(" %c\n",type==0?'-':'+');
            prev=t;
            type=1-type;
            now--;
        }
    }
    printf("%d",d[n]-prev);
    printf(" %c\n",type==0?'-':'+');
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:72:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   72 |     printf("%d",d[n]-prev);
      |             ~^  ~~~~~~~~~
      |              |      |
      |              int    long long int
      |             %lld
Main.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%lld %lld",&d[i],&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB OK, n=2 ans=1
2 Correct 1 ms 1868 KB OK, n=3 ans=1
3 Correct 1 ms 1868 KB OK, n=1 ans=1
4 Correct 1 ms 1868 KB OK, n=5 ans=1
5 Correct 1 ms 1868 KB OK, n=8 ans=1
6 Correct 1 ms 1868 KB OK, n=88 ans=1
7 Correct 1 ms 1868 KB OK, n=888 ans=1
8 Correct 2 ms 1996 KB OK, n=2000 ans=1
9 Correct 2 ms 1996 KB OK, n=2000 ans=1
10 Correct 2 ms 1996 KB OK, n=2000 ans=1
11 Correct 2 ms 1996 KB OK, n=2000 ans=1
12 Correct 1 ms 1868 KB OK, n=2 ans=1
13 Correct 1 ms 1868 KB OK, n=34 ans=1
14 Correct 1 ms 1868 KB OK, n=567 ans=1
15 Correct 2 ms 1868 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB OK, n=2 ans=1
2 Correct 1 ms 1868 KB OK, n=3 ans=1
3 Correct 1 ms 1868 KB OK, n=1 ans=1
4 Correct 1 ms 1868 KB OK, n=5 ans=1
5 Correct 1 ms 1868 KB OK, n=8 ans=1
6 Correct 1 ms 1868 KB OK, n=88 ans=1
7 Correct 1 ms 1868 KB OK, n=888 ans=1
8 Correct 2 ms 1996 KB OK, n=2000 ans=1
9 Correct 2 ms 1996 KB OK, n=2000 ans=1
10 Correct 2 ms 1996 KB OK, n=2000 ans=1
11 Correct 2 ms 1996 KB OK, n=2000 ans=1
12 Correct 1 ms 1868 KB OK, n=2 ans=1
13 Correct 1 ms 1868 KB OK, n=34 ans=1
14 Correct 1 ms 1868 KB OK, n=567 ans=1
15 Correct 2 ms 1868 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 1 ms 1868 KB OK, n=2 ans=2
23 Incorrect 2 ms 1868 KB Point #1 (3, 1) is not covered by the answer
24 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB OK, n=2 ans=1
2 Correct 1 ms 1868 KB OK, n=3 ans=1
3 Correct 1 ms 1868 KB OK, n=1 ans=1
4 Correct 1 ms 1868 KB OK, n=5 ans=1
5 Correct 1 ms 1868 KB OK, n=8 ans=1
6 Correct 1 ms 1868 KB OK, n=88 ans=1
7 Correct 1 ms 1868 KB OK, n=888 ans=1
8 Correct 2 ms 1996 KB OK, n=2000 ans=1
9 Correct 2 ms 1996 KB OK, n=2000 ans=1
10 Correct 2 ms 1996 KB OK, n=2000 ans=1
11 Correct 2 ms 1996 KB OK, n=2000 ans=1
12 Correct 1 ms 1868 KB OK, n=2 ans=1
13 Correct 1 ms 1868 KB OK, n=34 ans=1
14 Correct 1 ms 1868 KB OK, n=567 ans=1
15 Correct 2 ms 1868 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 1 ms 1868 KB OK, n=4 ans=2
23 Incorrect 1 ms 1868 KB Point #1 (3, -1) is not covered by the answer
24 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Point #2 (4, 2) is not covered by the answer
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB OK, n=2 ans=1
2 Correct 1 ms 1868 KB OK, n=3 ans=1
3 Correct 1 ms 1868 KB OK, n=1 ans=1
4 Correct 1 ms 1868 KB OK, n=5 ans=1
5 Correct 1 ms 1868 KB OK, n=8 ans=1
6 Correct 1 ms 1868 KB OK, n=88 ans=1
7 Correct 1 ms 1868 KB OK, n=888 ans=1
8 Correct 2 ms 1996 KB OK, n=2000 ans=1
9 Correct 2 ms 1996 KB OK, n=2000 ans=1
10 Correct 2 ms 1996 KB OK, n=2000 ans=1
11 Correct 2 ms 1996 KB OK, n=2000 ans=1
12 Correct 1 ms 1868 KB OK, n=2 ans=1
13 Correct 1 ms 1868 KB OK, n=34 ans=1
14 Correct 1 ms 1868 KB OK, n=567 ans=1
15 Correct 2 ms 1868 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 1 ms 1868 KB OK, n=2 ans=2
23 Incorrect 2 ms 1868 KB Point #1 (3, 1) is not covered by the answer
24 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB OK, n=2 ans=1
2 Correct 1 ms 1868 KB OK, n=3 ans=1
3 Correct 1 ms 1868 KB OK, n=1 ans=1
4 Correct 1 ms 1868 KB OK, n=5 ans=1
5 Correct 1 ms 1868 KB OK, n=8 ans=1
6 Correct 1 ms 1868 KB OK, n=88 ans=1
7 Correct 1 ms 1868 KB OK, n=888 ans=1
8 Correct 2 ms 1996 KB OK, n=2000 ans=1
9 Correct 2 ms 1996 KB OK, n=2000 ans=1
10 Correct 2 ms 1996 KB OK, n=2000 ans=1
11 Correct 2 ms 1996 KB OK, n=2000 ans=1
12 Correct 1 ms 1868 KB OK, n=2 ans=1
13 Correct 1 ms 1868 KB OK, n=34 ans=1
14 Correct 1 ms 1868 KB OK, n=567 ans=1
15 Correct 2 ms 1868 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 1 ms 1868 KB OK, n=2 ans=2
23 Incorrect 2 ms 1868 KB Point #1 (3, 1) is not covered by the answer
24 Halted 0 ms 0 KB -