oj.uz

Submission #600919

# Submission time Handle Problem Language Result Execution time Memory
600919 2022-07-21T09:09:44 Z balbit Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 212 KB 
// 我的心裡只有你沒有他
#pragma GCC optimize("O3", "unroll-loops")
#include "shortcut.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define pii pair <int, int >
#define f first
#define s second

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT


#define pb push_back
#define REP(i,n) for (int i = 0; i<(n); ++i)
#define REP1(i,n) for (int i = 1; i<=(n); ++i)


const int maxn = 1e6+5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int P[maxn], D[maxn]; // position, depth

vector<pii> Aval, Bval; // A is Da + Pa, B is Db - Pb

ll C[2][2], bigB[2], sbigB[2], whoB[2];


double t1=0,t2=0;

bool okay(int n, ll M, ll cost) {
    // for all D[a] + P[a] - D[b] + P[b] >= M, 
    clock_t t = clock();
    bug(M, cost);
    
    REP(r,2) REP(R, 2) {
        C[r][R] = -inf;
        bigB[r] = sbigB[r] = -inf;
        whoB[r] = -1;
    }

    int j = SZ(Bval)-1;
    if (M < 1e9 * 2+10) {
        REP(i,SZ(Aval)) {
            int a = Aval[i].s;
            while (j>=0 && Aval[i].f+Bval[j].f > M) {
                // work j
                int b = Bval[j].s;
                bug(a,b,Aval[i].f + Bval[i].f);
                REP(vx,2) {
                    ll val = D[b] +(vx?-1:1)*P[b];
                    if (val > bigB[vx]) {
                        sbigB[vx] = bigB[vx];
                        whoB[vx] = b;
                        bigB[vx] = val;
                    }else if (val > sbigB[vx]) {
                        sbigB[vx] = val;
                    }
                }
                --j;
            }
            REP(vx,2) {
                ll ka = cost-M+D[a]+(vx?-P[a]:P[a]);
                REP(vy,2) {
                    int bval = whoB[vy]==a?sbigB[vy] : bigB[vy];
                    MX(C[vx][vy], (ka + bval));
                }
            }
            if (C[0][0] > -C[1][1]) return 0;
            if (C[0][1] > -C[1][0]) return 0;
        }
    }else{
        REP(i,SZ(Aval)) {
            int a = Aval[i].s;
            while (j>=0 && Aval[i].f+Bval[j].f > M) {
                int b = Bval[j].s;
                REP(vx,2) {
                    MX(bigB[vx], D[b] +(vx?-P[b]:P[b]));
                }
                --j;
            }
            REP(vx,2) {
                ll ka = cost-M+D[a]+(vx?-P[a]:P[a]);
                REP(vy,2) {
                    MX(C[vx][vy], (ka + bigB[vy]));
                }
            }
            if (C[0][0] > -C[1][1]) return 0;
            if (C[0][1] > -C[1][0]) return 0;
        }
    }
    
    t1 += (clock()-t) / (double)CLOCKS_PER_SEC;
    t = clock();

    // REP(X,2) REP(Y,2) C[X][Y] += cost-M;

    // bug(C[0][0], C[0][1], C[1][0], C[1][1]);

    vector<ll> ya; 

    signed i00=n, i01=-1, i10=0,i11=n-1;

     t = clock();

    bool ok = 0;
    while (i00-1>=0 && P[i00-1] >= C[0][0]) --i00;
    while (i01+1 <n && P[i01+1] <= -C[0][1]) ++i01;

    REP(a, n) {
        ll X = P[a];

        if (C[0][0] - X >= C[1][0] + X) {
            while (i00-1>=0 && P[i00-1] >= C[0][0]-X) --i00;
        }else{
            while (i00<n && P[i00] < C[1][0] + X) ++ i00;
        }

        if (-C[0][1] + X <= -C[1][1] - X) {
            while (i01+1 <n && P[i01+1] <= -C[0][1] + X) ++i01;
        }else{
            while (i01 >= 0 && P[i01] > -C[1][1] - X) --i01;
        }

        if (i00 <= i01) {
            ok = 1; break;
        }
    }

    t2 += (clock()-t) / (double)CLOCKS_PER_SEC;

    return ok;

    // conditions: Pa + Da + 


}

long long find_shortcut(signed n, std::vector<signed> l, std::vector<signed> _d, signed _c)
{
    // watermelon 4A orz
    bug(1,2);
    P[0] = 0;
    REP(i,n-1) P[i+1] = P[i] + l[i];
    // P[n] = inf*2;
    REP(i,n) D[i] = _d[i];

    REP(i,n) {
        Aval.pb({D[i] + P[i], i});
        Bval.pb({D[i] - P[i], i});
    }

    sort(ALL(Aval));
    sort(ALL(Bval));

    int lb=P[n-1]/3, rb=P[n-1]+2e9+100;

    while (lb != rb) {
        ll M = (lb+rb)/2;
        if (okay(n,M,_c)) {
            rb = M;
        }else {
            lb = M+1;
        }
    }

    bug(lb);
    return lb;
}


/*


4 10
10 20 20
0 40 0 30


9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0

3 10
1 1
0 1000 0

*/

//
#ifdef BALBIT
signed main(){

//    bug(hi);
   int n; cin>>n;
   REP(www, 1) {
       vector<signed> l, d;
       REP(i,n-1) {
           l.pb(rand()%1000000000);
       }
       REP(i,n) {
           d.pb(rand()%1000000000);
       }
       bug(find_shortcut(n, l, d, 222));
       bug(t1,t2);
   }
}
#endif

Compilation message

shortcut.cpp: In function 'bool okay(long long int, long long int, long long int)':
shortcut.cpp:117:27: warning: unused variable 'i10' [-Wunused-variable]
  117 |     signed i00=n, i01=-1, i10=0,i11=n-1;
      |                           ^~~
shortcut.cpp:117:33: warning: unused variable 'i11' [-Wunused-variable]
  117 |     signed i00=n, i01=-1, i10=0,i11=n-1;
      |                                 ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 212 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 212 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 212 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 212 KB n = 10, 1000000343 is a correct answer
18 Incorrect 1 ms 212 KB n = 10, incorrect answer: jury 3189 vs contestant 3392
19 Halted 0 ms 0 KB -