oj.uz

Submission #997380

# Submission time Handle Problem Language Result Execution time Memory
997380 2024-06-12T08:18:14 Z doducanh Palembang Bridges (APIO15_bridge) C++14
22 / 100
 184 ms 6040 KB 
#include <bits/stdc++.h>

using namespace std;
#define ii pair<int,int>
const int maxn=1e5+7;
struct nguoi
{
    int xo,yo,xt,yt;
};
nguoi a[maxn];
int k,n;
vector<ii>v;
vector<int>tmp;
long long f(int t)
{
    long long sum=0;
    for(auto [x,y]:v){
        sum+=(abs(x-t)+abs(y-t)+1);
    }
    return sum;
}
main()
{
    cin>>k>>n;

    long long delt=0;
    for(int i=1;i<=n;i++){
        char xo,xt;
        cin>>xo>>a[i].yo>>xt>>a[i].yt;
        a[i].xo=(xo=='B');
        a[i].xt=(xt=='B');
        if(xo==xt){
            delt+=abs(a[i].yt-a[i].yo);
        }
        else{
            tmp.push_back(a[i].yo);
            tmp.push_back(a[i].yt);
            v.push_back({a[i].yo,a[i].yt});
        }

    }
    int l=0,r=1e9+7;
    while(r-l>1000){
        int m1=l+(r-l)/3;
        int m2=r-(r-l)/3;
        if(f(m1)<f(m2)){
            r=m2;
        }
        else l=m1;
    }
//    for(auto [x,y]:v){
//        cout<<x<<" "<<y<<"\n";
//    }
    long long ans=LLONG_MAX;
    for(auto i=l;i<=r;i++){
        ans=min(ans,f(i));
//        if(f(i)==18)cout<<i;
//        cout<<f(i)<<"\n";
    }
    cout<<ans+delt;
    return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message

bridge.cpp: In function 'long long int f(int)':
bridge.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [x,y]:v){
      |              ^
bridge.cpp: At global scope:
bridge.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main()
      | ^~~~

Subtask #1
8.0 / 8.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 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 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

Subtask #2
14.0 / 14.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 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 126 ms 3624 KB Output is correct
13 Correct 184 ms 3528 KB Output is correct
14 Correct 124 ms 4552 KB Output is correct
15 Correct 91 ms 3780 KB Output is correct
16 Correct 172 ms 5312 KB Output is correct
17 Correct 154 ms 5820 KB Output is correct
18 Correct 148 ms 5564 KB Output is correct
19 Correct 155 ms 6040 KB Output is correct
20 Correct 155 ms 5512 KB Output is correct
21 Correct 152 ms 5568 KB Output is correct

Subtask #3
0 / 9.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

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

Subtask #5
0 / 37.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 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -