oj.uz

Submission #95674

# Submission time Handle Problem Language Result Execution time Memory
95674 2019-02-02T07:32:40 Z jeff Gap (APIO16_gap) C++14
70 / 100
 2000 ms 525312 KB 
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
 
inline unsigned long long mde(unsigned long long a, unsigned long long b, unsigned long long c) {
    unsigned long long t = 0, y = 0, z = 0, i;
    stack<unsigned long long> st;
    while (b) st.push(b % 2), b /= 2;
    while (!st.empty()) {
        z <<= 1;
        y <<= 1;
        z += a * st.top();
        st.pop();
        y += z / (1LL << 62);
        z %= (1LL << 62);
    }
    t += y / c;
    y %= c;
    for (i = 0; i < 62; ++i) {
        y <<= 1;
        z <<= 1;
        t <<= 1;
        y += z / (1LL << 62);
        z %= (1LL << 62);
        t += y / c;
        y %= c;
    }
    return t;
}
 
vector<long long> v;

long long findGap(int T, int N) {
    long long l, r, y, z, ls = -1, rs = 0, a, b = 0, i;
    if (T == 1) {
        l = 0;
        r = 1000000000000000000;
        while (l < r) {
            MinMax(l, r, &a, &b);
            if (a >= b) break;
            v.push_back(a);
            v.push_back(b);
            l = a - 1;
            r = b + 1;
        }
        if (a > -1 && b > -1) v.push_back(a);
        sort(v.begin(), v.end());
        for (i = 1; i < v.size(); ++i) rs = max(rs, v[i] - v[i - 1]);
        return rs;
    }
    MinMax(0, 1000000000000000000, &y, &z);
    for (i = 0; i < N - 1; ++i) {
        a = y + mde(z - y, i, N - 1);
        b = y + mde(z - y, i + 1, N - 1) - 1;
        if (a >= b) continue;
        MinMax(a, b, &l, &r);
        if (l < 0 && r < 0) continue;
        if (ls > -1) rs = max(rs, l - ls);
        ls = r;
    }
	return max(rs, z - ls);
}

Compilation message

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 1; i < v.size(); ++i) rs = max(rs, v[i] - v[i - 1]);
                     ~~^~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1449 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 1291 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 1290 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 1371 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 1381 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1680 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 1619 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1608 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 1676 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 1565 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 2094 ms 355056 KB Time limit exceeded
12 Execution timed out 2081 ms 266548 KB Time limit exceeded
13 Execution timed out 2072 ms 263208 KB Time limit exceeded
14 Execution timed out 2083 ms 311996 KB Time limit exceeded
15 Execution timed out 2089 ms 263248 KB Time limit exceeded
16 Execution timed out 2073 ms 263736 KB Time limit exceeded
17 Execution timed out 2054 ms 263664 KB Time limit exceeded
18 Execution timed out 2051 ms 263752 KB Time limit exceeded
19 Execution timed out 2050 ms 263356 KB Time limit exceeded
20 Execution timed out 2056 ms 263288 KB Time limit exceeded
21 Execution timed out 2031 ms 263884 KB Time limit exceeded
22 Execution timed out 2061 ms 263924 KB Time limit exceeded
23 Execution timed out 2078 ms 264100 KB Time limit exceeded
24 Execution timed out 2062 ms 264132 KB Time limit exceeded
25 Execution timed out 2085 ms 264032 KB Time limit exceeded
26 Execution timed out 2077 ms 264016 KB Time limit exceeded
27 Execution timed out 2111 ms 263908 KB Time limit exceeded
28 Execution timed out 2015 ms 263916 KB Time limit exceeded
29 Execution timed out 2019 ms 263984 KB Time limit exceeded
30 Execution timed out 2044 ms 263948 KB Time limit exceeded
31 Runtime error 1723 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 1664 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 57 ms 760 KB Output is correct
17 Correct 57 ms 760 KB Output is correct
18 Correct 58 ms 804 KB Output is correct
19 Correct 58 ms 888 KB Output is correct
20 Correct 51 ms 632 KB Output is correct
21 Correct 230 ms 1248 KB Output is correct
22 Correct 229 ms 1272 KB Output is correct
23 Correct 224 ms 1272 KB Output is correct
24 Correct 226 ms 1400 KB Output is correct
25 Correct 217 ms 1400 KB Output is correct
26 Correct 227 ms 1272 KB Output is correct
27 Correct 232 ms 1272 KB Output is correct
28 Correct 228 ms 1272 KB Output is correct
29 Correct 229 ms 1352 KB Output is correct
30 Correct 201 ms 1272 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct