oj.uz

Submission #209508

# Submission time Handle Problem Language Result Execution time Memory
209508 2020-03-14T12:29:39 Z model_code Snail (NOI18_snail) C++17
100 / 100
 7 ms 632 KB 
#include <cstdio>
#include <algorithm>
#include <assert.h>
#define INF 1012345678012345678LL
#define BIG 1000000000000LL
using namespace std;
typedef long long ll;
// height, number of phases, phase
ll H;
int N;
ll P[10010];
ll simulate[20010];
ll increment = 0; // increment every cycle
bool printed = 0;
int main(void) {
    scanf("%lld%d", &H, &N);
    assert(1<=H && H<=BIG);
    assert(1<=N && N<=10000);
    for (int i=0;i<N;i++) {
        scanf("%lld", &P[i]);
        assert(-BIG<=P[i] && P[i]<=BIG);
    }
    // simulate for 2 days
    simulate[0] = 0; // height at start of each phase
    for (int i=0;i<2*N;i++) { // people may forget this
        simulate[i+1] = max(simulate[i]+P[i%N], 0LL); // people may leave out max
        if (simulate[i+1] >= H) { // >= is intended
            printf("%d %d\n", i/N, i%N);
            printed = 1;
            break;
        }
    }
    if (!printed) {
        for (int i=0;i<N;i++) {
            increment += P[i]; // should not overflow, but can underflow
            // oh no what if it underflows?
            if (increment <= -H) { // if it ever goes back above 0, then it must be possible within first 2N phases
                printf("-1 -1\n");
                printed = true;
                break;
            }
        }
    }
    if (!printed) {
        // check if it goes negative anywhere
        if (increment <= 0) {
            // not possible anymore
            printf("-1 -1\n");
            printed = true;
        } else {
            ll bestDays = INF;
            int phase = 0;
            for (int i=0;i<N;i++) {
                ll days = 1+(H-simulate[N+i+1]+increment-1)/increment;
                if (bestDays > days) {
                    bestDays = days;
                    phase = i;
                }
            }
            printf("%lld %d\n", bestDays, phase);
            printed = true;
        }
    }
    return 0;
}

Compilation message

snail.cpp: In function 'int main()':
snail.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%d", &H, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~
snail.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &P[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 7 ms 504 KB Output is correct

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 6 ms 504 KB Output is correct
23 Correct 6 ms 376 KB Output is correct
24 Correct 6 ms 376 KB Output is correct
25 Correct 6 ms 376 KB Output is correct
26 Correct 7 ms 504 KB Output is correct
27 Correct 6 ms 504 KB Output is correct
28 Correct 7 ms 504 KB Output is correct
29 Correct 7 ms 504 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 6 ms 508 KB Output is correct
32 Correct 6 ms 632 KB Output is correct