Submission #600700

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600700	2022-07-21T07:11:10 Z	balbit	Shortcut (IOI16_shortcut)	C++14	0 / 100	0 ms	212 KB

shortcut

// 我的心裡只有你沒有他

#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

bool okay(int n, ll M, ll cost) {
    // for all D[a] + P[a] - D[b] + P[b] >= M, 

    bug(M, cost);
    
    vector<vector<ll> > C(2, vector<ll> (2,-inf));

    // C[0][0] =>  X + Y >= C[0][0],
    // C[1][0] => -X + Y >= C[1][0], etc

    vector<ll > bigB(2, -inf);

    int j = SZ(Bval)-1;
    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) {
                MX(bigB[vx], D[b] +(vx?-1:1)*P[b]);
            }
            --j;
        }
        REP(vx,2)REP(vy,2) {
            MX(C[vx][vy], (cost-M+D[a] + (vx?-1:1)*P[a] + bigB[vy]));
        }
    }

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

    REP(a, n) {
        ll X = P[a];
        ll lb = max(C[0][0]-X, C[1][0] + X);
        ll rb = min(-C[0][1]+X, -C[1][1]-X);
        bug(X, lb, rb);
        if (lb > rb) continue;
        int it = lower_bound(P, P+n, lb) - P;
        if (it < n && P[it] <= rb) {
            return 1;
        }
    }

    return 0;

    // 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=0, rb=3e18;

    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
*/

//
//signed main(){
////    ll hi = find_shortcut(9, {10, 10, 10, 10, 10, 10, 10, 10},
////{20, 0, 30, 0, 0, 40, 0, 40, 0}, 30);
////    bug(hi);
//    int n; cin>>n;
//    REP(www, 100) {
//        vector<int> l, d;
//        REP(i,n-1) {
//            l.pb(rand()%1000000);
//        }
//        REP(i,n) {
//            d.pb(rand()%1000000);
//        }
//        bug(find_shortcut(n, l, d, 1));
//    }
//}

Subtask #1
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #2
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #4
0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #5
0 / 33.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #6
0 / 22.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #7
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #8
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Incorrect	212 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Submission #600700

Compilation message