oj.uz

Submission #59807

# Submission time Handle Problem Language Result Execution time Memory
59807 2018-07-23T07:01:49 Z 강태규(#1723) Sparklers (JOI17_sparklers) C++11
0 / 100
 3 ms 600 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, k, t;
int x[100001];

const int inf = 1e9 + 7;
llong a[100001];

int check(int s) {
    for (int i = 1; i <= n; ++i) {
        a[i] = 2ll * i * t * s - x[i];
    }
    if (a[1] > a[n]) return 0;
    pll mx(a[k], k), mn(a[k], k);
    for (int i = 1; i <= n; ++i) {
        mx = max(mx, pll(a[i], i));
        mn = min(mn, pll(a[i], i));
    }
    if (mn.second > k) return 0;
    if (mx.second < k) return 0;
    int pl = 0, pr = 0;
    llong ml = a[k], mr = a[k];
    for (int i = k - 1; i > 0; --i) {
        ml = max(ml, a[i]);
        if (a[i] <= a[k]) {
            pl = i;
            break;
        }
    }
    for (int i = k + 1; i <= n; ++i) {
        mr = min(mr, a[i]);
        if (a[k] <= a[i]) {
            pr = i;
            break;
        }
    }
    for (int i = k, j = k; pl || pr; ) {
        if (pl && ml <= a[j]) {
            i = pl;
            ml = a[i];
            pl = 0;
            for (int t = i - 1; t > 0; --t) {
                ml = max(ml, a[t]);
                if (a[t] <= a[i]) {
                    pl = t;
                    break;
                }
            }
        }
        else if (pr && a[i] <= mr) {
            j = pr;
            mr = a[j];
            pr = 0;
            for (int t = j + 1; t <= n; ++t) {
                mr = min(mr, a[t]);
                if (a[j] <= a[t]) {
                    pr = t;
                    break;
                }
            }
        }
        else return 0;
    }
    pl = 0; pr = 0;
    ml = a[1]; mr = a[n];
    for (int i = 2; i <= mn.second; ++i) {
        ml = max(ml, a[i]);
        if (a[i] <= a[1]) {
            pl = i;
            break;
        }
    }
    for (int i = n - 1; mx.second <= i; --i) {
        mr = min(mr, a[i]);
        if (a[n] <= a[i]) {
            pr = i;
            break;
        }
    }
    for (int i = 1, j = n; pl && pr; ) {
        if (pl && ml <= a[j]) {
            i = pl;
            ml = a[i];
            pl = 0;
            for (int t = i - 1; t > 0; --t) {
                ml = max(ml, a[t]);
                if (a[t] <= a[i]) {
                    pl = t;
                    break;
                }
            }
        }
        else if (pr && a[i] <= mr) {
            j = pr;
            mr = a[j];
            pr = 0;
            for (int t = j + 1; t <= n; ++t) {
                mr = min(mr, a[t]);
                if (a[j] <= a[t]) {
                    pr = t;
                    break;
                }
            }
        }
        else return 0;
    }
    return 1;
}

int main() {
    scanf("%d%d%d", &n, &k, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", x + i);
    }
    if (x[n] == 0) {
        printf("0\n");
        return 0;
    }
    
    int s = 1, e = inf / t + 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (check(m)) e = m;
        else s = m + 1;
    }
    printf("%d\n", s);
	return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", x + i);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Incorrect 2 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Incorrect 2 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Incorrect 2 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -