oj.uz

Submission #921799

# Submission time Handle Problem Language Result Execution time Memory
921799 2024-02-04T10:26:45 Z Ludissey Palembang Bridges (APIO15_bridge) C++14
0 / 100
 142 ms 512 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<pair<int,int>> notSame; // min et le max
int N;

struct traj { 
    int l,r;
    double mid; 
};
vector<traj> a;

int cmp(int x1, int x2){
    int s=0;
    for (int i = 0; i < a.size(); i++)
    {
        int s1=abs(x1-a[i].l)+1+abs(x1-a[i].r);
        int s2=abs(x2-a[i].l)+1+abs(x2-a[i].r);
        s+=min(s1,s2);
    }
    return s;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,k; cin >> k >> n;
    N=n;
    int sum=0;
    vector<int> b;
    for (int i = 0; i < n; i++){
        char p,q; int s,t; cin >> p >> s >> q >> t;
        if(p!=q) {
            double mid=(((double)s+(double)t)/(double)2);
            traj element=traj{min(s, t), max(s,t), mid};
            a.push_back(element);
            b.push_back(s);
            b.push_back(t);
        }else {
            sum+=abs(s-t);
        }
    }
    sort(a.begin(),a.end(),[](traj &_a, traj &_b){ return _a.mid < _b.mid; });
    sort(b.begin(),b.end());
    N=a.size();  
    int mn=1e12;
    int BESTL, BESTR;
    if(N==0) mn=0;
    for (int i = 0; i < 2*N; i++)
    {
        int l=i+1,r=(2*N)-1;
        while((r-l)>10){
            int mid=(l+r)/2;
            int midLEFT=(l+mid);
            int midRIGHT=(mid+1+r)/2;
            if(cmp(b[i], b[midLEFT])>cmp(b[i], b[midRIGHT])){
                l=midLEFT+1;
            }else{
                r=midRIGHT-1;
            }
        }
        for (int j = l; j <= r; j++)
        {
            if(mn>cmp(b[i],b[j])) { 
                BESTL=b[i]; BESTR=b[j]; 
            }
            mn=min(mn,cmp(b[i],b[j]));
        }
    }
    cerr << BESTL << " " << BESTR <<"\n";

    cout << mn+sum << "\n";
    return 0;
}

Compilation message

bridge.cpp: In function 'long long int cmp(long long int, long long int)':
bridge.cpp:16:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<traj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 142 ms 348 KB Output is correct
4 Incorrect 64 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 140 ms 500 KB Output is correct
4 Incorrect 64 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -