oj.uz

Submission #921814

# Submission time Handle Problem Language Result Execution time Memory
921814 2024-02-04T10:44:27 Z Ludissey Palembang Bridges (APIO15_bridge) C++14
9 / 100
 245 ms 600 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;
    int mid; 
};
vector<traj> a;

int calculate(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{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)/2;
            int midRIGHT=(mid+1+r)/2;
            if(calculate(b[i], b[midLEFT])>calculate(b[i], b[midRIGHT])){
                l=midLEFT+1;
            }else{
                r=midRIGHT-1;
            }
        }
        for (int j = l; j <= r; j++)
        {
            if(mn>calculate(b[i],b[j])) { 
                BESTL=b[i]; BESTR=b[j]; 
            }
            mn=min(mn,calculate(b[i],b[j]));
        }
    }
    cout << mn+sum << "\n";
    return 0;
}

Compilation message

bridge.cpp: In function 'long long int calculate(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++)
      |                     ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:36:37: warning: narrowing conversion of 'mid' from 'double' to 'long long int' [-Wnarrowing]
   36 |             traj element=traj{s, t, mid};
      |                                     ^~~
bridge.cpp:48:9: warning: variable 'BESTL' set but not used [-Wunused-but-set-variable]
   48 |     int BESTL, BESTR;
      |         ^~~~~
bridge.cpp:48:16: warning: variable 'BESTR' set but not used [-Wunused-but-set-variable]
   48 |     int BESTL, BESTR;
      |                ^~~~~

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 Incorrect 245 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 500 KB Output is correct

Subtask #4
0 / 32.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 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 560 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 200 ms 488 KB Output is correct
14 Correct 197 ms 496 KB Output is correct
15 Correct 188 ms 348 KB Output is correct
16 Correct 16 ms 488 KB Output is correct
17 Correct 53 ms 476 KB Output is correct
18 Correct 27 ms 348 KB Output is correct
19 Incorrect 186 ms 492 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 194 ms 488 KB Output is correct
14 Correct 190 ms 492 KB Output is correct
15 Correct 204 ms 484 KB Output is correct
16 Correct 15 ms 348 KB Output is correct
17 Correct 53 ms 348 KB Output is correct
18 Correct 26 ms 348 KB Output is correct
19 Incorrect 196 ms 492 KB Output isn't correct
20 Halted 0 ms 0 KB -