oj.uz

Submission #549879

# Submission time Handle Problem Language Result Execution time Memory
549879 2022-04-16T17:54:11 Z ala2 Palembang Bridges (APIO15_bridge) C++14
31 / 100
 1437 ms 2748 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
#define B begin()
#define E end()
using namespace std;
vector<pair<int,int>>v;
int f(int x,int y)
{
    int g=0;
    for(int i=0;i<v.size();i++)
    {
        g+=min( abs(v[i].F-x )+abs(v[i].S-x) ,abs(v[i].F-y )+abs(v[i].S-y));
    }
    return g;
}
signed main()
{
    int n,k;
    cin>>k>>n;
    int ans=0;

    for(int i=0;i<n;i++)
    {
        char x,y;
        int a,b;
        cin>>x>>a>>y>>b;
        if(x==y)
        {
            ans+=abs(a-b);
        }
        else v.pb({a,b}),ans++;
    }
    if(k==1){
    sort(v.B,v.E);
    int x=v.size()/2;
    int l=-3,r=1000000005;
    int y=200;
    int mn=1e18;
    while(y--)
    {
        int mid1=l+(r-l)/3;
        int mid2=l+((r-l)/3)*2;
        mn=min(mn,f(mid1,1e18));
        mn=min(mn,f(mid2,1e18));
        if(f(mid2,1e18)<=f(mid1,1e18))
        {
            l=mid1;
        }
        else
            r=mid2;


    }
    mn=min(mn,f(l,1e18));
    cout<<min(mn,f(r,1e18))+ans<<endl;
    return 0;
    }
    // ___________________________________
    int mn=1e18;
    if(v.size()==0)
    {
        mn=0;
    }
    for(int i=0;i<v.size();i++)
    {
        for(int j=i;j<v.size();j++)
        {
            mn=min(mn,f(v[i].S,v[j].S));
        }
    }
    cout<<mn+ans<<endl;

}

Compilation message

bridge.cpp: In function 'long long int f(long long int, long long int)':
bridge.cpp:13:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:38:9: warning: unused variable 'x' [-Wunused-variable]
   38 |     int x=v.size()/2;
      |         ^
bridge.cpp:67:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
bridge.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int j=i;j<v.size();j++)
      |                     ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 312 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 316 KB Output is correct
11 Correct 2 ms 312 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 316 KB Output is correct
6 Correct 3 ms 312 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 154 ms 2552 KB Output is correct
13 Correct 206 ms 2720 KB Output is correct
14 Correct 174 ms 2748 KB Output is correct
15 Correct 128 ms 1600 KB Output is correct
16 Correct 177 ms 2704 KB Output is correct
17 Correct 191 ms 2620 KB Output is correct
18 Correct 187 ms 2692 KB Output is correct
19 Correct 200 ms 2692 KB Output is correct
20 Correct 186 ms 2616 KB Output is correct
21 Correct 191 ms 2624 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 1291 ms 328 KB Output is correct
14 Correct 1319 ms 332 KB Output is correct
15 Correct 1268 ms 340 KB Output is correct
16 Correct 43 ms 340 KB Output is correct
17 Correct 217 ms 308 KB Output is correct
18 Correct 74 ms 300 KB Output is correct
19 Correct 1334 ms 340 KB Output is correct
20 Correct 1364 ms 340 KB Output is correct
21 Correct 1402 ms 340 KB Output is correct
22 Correct 1360 ms 340 KB Output is correct
23 Correct 1409 ms 340 KB Output is correct
24 Incorrect 1421 ms 340 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 2 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 296 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 1398 ms 316 KB Output is correct
14 Correct 1437 ms 320 KB Output is correct
15 Correct 1367 ms 340 KB Output is correct
16 Correct 42 ms 296 KB Output is correct
17 Correct 218 ms 308 KB Output is correct
18 Correct 72 ms 296 KB Output is correct
19 Correct 1416 ms 340 KB Output is correct
20 Correct 1426 ms 340 KB Output is correct
21 Correct 1420 ms 340 KB Output is correct
22 Correct 1437 ms 340 KB Output is correct
23 Correct 1388 ms 460 KB Output is correct
24 Incorrect 1390 ms 340 KB Output isn't correct
25 Halted 0 ms 0 KB -