oj.uz

Submission #949560

# Submission time Handle Problem Language Result Execution time Memory
949560 2024-03-19T11:05:41 Z definitelynotmee Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 432 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define O_O
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double dbl;
typedef long double dbll; 
const ll INFL = 4e18+25;
const int INF = 1e9+42;
const double EPS = 1e-7;
const int MOD = (1<<23)*17*7 + 1; // 998244353
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

vector<ll> x;

struct rhombus{
    ll d1mn, d1mx, d2mn, d2mx;

    rhombus(ll a, ll b, ll c, ll d) : d1mn(a), d1mx(b), d2mn(c), d2mx(d){}

    rhombus(ll x, ll y, ll dist){
        ll d1 = x+y, d2 = x-y;

        d1mn = d1-dist, d1mx = d1+dist, d2mn = d2-dist, d2mx = d2+dist;
    }

    bool in(ll x, ll y){
        ll d1 = x+y, d2 = x-y;
        return d1mn <= d1 && d1 <= d1mx && d2mn <= d2 && d2 <= d2mx;
    }

    rhombus operator+(rhombus b){
        return rhombus(max(d1mn, b.d1mn), min(d1mx, b.d1mx), max(d2mn, b.d2mn), min(d2mx, b.d2mx));
    }
};

bool test_poss(int n, vector<int> l, vector<int> d, int c, ll target){
    
    rhombus resp(-INFL,INFL,-INFL,INFL);
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(abs(x[i]-x[j]) + d[i] + d[j] > target)
                resp = resp + rhombus(x[i], x[j], target - (c + d[i] + d[j]));
        }
    }

    // cerr << resp.d1mn << ' ' << resp.d1mx << ' ' << resp.d2mn << ' ' << resp.d2mx << '\n';

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(resp.in(x[i],x[j]))
                return 1;
        }
    }

    return 0;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    
    x.resize(n);

    x[0] = 0;

    for(int i = 1; i < n; i++)
        x[i] = x[i-1] + l[i-1];
    
    ll ini = 0, fim = 1e16;

    while(ini != fim){
        ll m = (ini + fim)>>1;

        // cerr << ini << ' ' << fim << ' ' << m << endl;
        if(test_poss(n,l,d,c,m))
            fim = m;
        else ini = m+1;
    }

    return ini;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 432 KB n = 2, 62 is a correct answer
6 Correct 0 ms 344 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Incorrect 1 ms 348 KB n = 2, incorrect answer: jury 3000000000 vs contestant 0
12 Halted 0 ms 0 KB -