Submission #1109939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109939		simona1230	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2 ms	504 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

int k,n,num,other;
pair<int,int> p[100001];

bool cmp(pair<int,int> p1,pair<int,int> p2)
{
    return p1.first+p1.second<p2.first+p2.second;
}

void read()
{
    cin>>k>>n;
    for(int i=1;i<=n;i++)
    {
        char c1,c2;
        int x,y;
        cin>>c1>>x>>c2>>y;

        if(c1==c2)other+=abs(x-y);
        else
        {
            num++;
            p[num]={min(x,y),max(x,y)};
        }
    }

    sort(p+1,p+num+1,cmp);

    if(num==0)
    {
        cout<<other<<endl;
        exit(0);
    }
}

void solve1()
{
    vector<int> v;

    for(int i=1;i<=num;i++)
    {
        v.push_back(p[i].first);
        v.push_back(p[i].second);
    }

    sort(v.begin(),v.end());

    int x=v[v.size()/2];

    int ans=other+num;
    for(int i=0;i<v.size();i++)
    {
        ans+=abs(v[i]-x);
    }

    cout<<ans<<endl;
}

void solve2()
{
    int ans=1e18;
    if(num==1)
    {
        cout<<other+1+p[1].second-p[1].first<<endl;
        exit(0);
    }

    for(int i=1;i<num;i++)
    {
        vector<int> v1,v2;
        for(int j=1;j<=num;j++)
        {
            if(j<=i)
            {
                v1.push_back(p[j].first);
                v1.push_back(p[j].second);
            }
            else
            {
                v2.push_back(p[j].first);
                v2.push_back(p[j].second);
            }
        }

        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());

        int x1=v1[v1.size()/2];
        int x2=v2[v2.size()/2];

        int curr=0;
        for(int j=0;j<v1.size();j++)
            curr+=abs(v1[j]-x1);
        for(int j=0;j<v2.size();j++)
            curr+=abs(v2[j]-x2);

        ans=min(ans,curr+other+num);
    }
    cout<<ans<<endl;
}

int main()
{
    read();
    if(k==1)solve1();
    else solve2();
    return 0;
}

/*
 2 5
 B 0 A 4
 B 1 B 3
 A 5 B 7
 B 2 A 6
 B 1 A 7

1 3
A 1 B 1
A 5 B 5
A 6 B 6
*/

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:63:13: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   63 |     int ans=1e18;
      |             ^~~~
bridge.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j=0;j<v1.size();j++)
      |                     ~^~~~~~~~~~
bridge.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j=0;j<v2.size();j++)
      |                     ~^~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37