Submission #1202938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202938		Aviansh	Shortcut (IOI16_shortcut)	C++20	71 / 100	2094 ms	1352 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>

using namespace std;

bool check(long long x, int n, long long pts[], vector<int> &d, int c){
    long long up1,up2,do1,do2;
    up1=2e18;
    up2=2e18;
    do1=-2e18;
    do2=-2e18;
    //d[i]+d[j]+|pts[i]-y|+|pts[j]-z| <= x
    //1:
    //y+z>=d[i]+d[j]+pts[i]+pts[j]-x+c
    //y+z<=x-d[i]-d[j]+pts[i]+pts[j]-c
    //2:
    //y-z<=x-d[i]-d[j]+pts[i]-pts[j]-c
    //y-z>=d[i]+d[j]-x+pts[i]-pts[j]+c
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            long long dist1 = d[i]+d[j]+pts[j]-pts[i];
            if(dist1<=x){
                continue;
            }
            up1=min(up1,x-d[i]-d[j]+pts[i]+pts[j]-c);
            do1=max(do1,d[i]+d[j]+pts[i]+pts[j]-x+c);
            up2=min(up2,x-d[i]-d[j]+pts[i]-pts[j]-c);
            do2=max(do2,d[i]+d[j]-x+pts[i]-pts[j]+c);
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            long long y = pts[i];
            long long z = pts[j];
            if(y+z>=do1&&y+z<=up1&&y-z>=do2&&y-z<=up2){
                return 1;
            }
        }
    }
    return 0;
}

long long find_shortcut(int n, vector<int> lens, vector<int> d, int c){
    long long lo=0;
    long long hi=2e18;
    long long pts[n];
    pts[0]=0;
    for(int i = 0;i<n-1;i++){
        pts[i+1]=pts[i]+lens[i];
    }
    while(lo<hi){
        long long mid = (lo+hi)/2;
        if(check(mid,n,pts,d,c)){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }
    return lo;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3