oj.uz

Submission #1054302

# Submission time Handle Problem Language Result Execution time Memory
1054302 2024-08-12T08:32:00 Z FaustasK Palembang Bridges (APIO15_bridge) C++14
22 / 100
 98 ms 13384 KB 
#include <bits/stdc++.h>

using namespace std;

struct gyventojas
{
    char p;
    int s;
    char q;
    int t;
};

const int maxn = 100000;
const long long daug = 1000000000000000;

int k, n, kiek;
gyventojas M[maxn];

vector <int> reikalingi;
vector <int> nereikalingi;
vector <int> medianai;
vector <int> unikalus;
set <int> buvo;

long long skaiciuok_keliu_suma(int tiltas1, int tiltas2)
{
    long long ats = 0;
    if(kiek>0)
    {
        if(k == 1)
        {
            for(int i = 0; i<reikalingi.size(); i++)
            {
                int j = reikalingi[i];
                ats += abs(M[j].s - tiltas1) + abs(M[j].t - tiltas1);
            }
        }
        else
        {
            for(int f = 0; f<reikalingi.size(); f++)
            {
                int x = reikalingi[f];
                int a1 = abs(M[x].s - tiltas1) + abs(M[x].t - tiltas1);
                int a2 = abs(M[x].s - tiltas2) + abs(M[x].t - tiltas2);
                ats += min(a1, a2);
            }
        }
    }
    for(int i = 0; i<nereikalingi.size(); i++)
    {
        int j = nereikalingi[i];
        ats += abs(M[j].s - M[j].t);
    }
    return ats + reikalingi.size();
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> k >> n;
    long long A_puse = 0;
    long long B_puse = 0;
    for(int i = 0; i<n; i++)
    {
        cin >> M[i].p >> M[i].s >> M[i].q >> M[i].t;
        if(M[i].p != M[i].q)
        {
            reikalingi.push_back(i);
            medianai.push_back(M[i].s);
            medianai.push_back(M[i].t);
            if(buvo.find(M[i].s) == buvo.end())
            {
                buvo.insert(M[i].s);
                unikalus.push_back(M[i].s);
            }
            if(buvo.find(M[i].t) == buvo.end())
            {
                buvo.insert(M[i].t);
                unikalus.push_back(M[i].t);
            }
        }
        else nereikalingi.push_back(i);
    }
    sort(medianai.begin(), medianai.end());
    kiek = reikalingi.size();

    if(k==1)
    {
        if(kiek > 0) cout << skaiciuok_keliu_suma(medianai[medianai.size()/2], -1);
        else cout << skaiciuok_keliu_suma(-1, -1);
    }
    else
    {
        /*long long maz_ats = 1000000000000000;
        for(int i = 0; i<medianai.size(); i++)
        {
            for(int j = 0; j<medianai.size(); j++)
            {
                if(i == j) continue;
                maz_ats = min(maz_ats, skaiciuok_keliu_suma(medianai[i], medianai[j]));
            }
        }
        cout << maz_ats;*/
        int ka = 0, de = 1;
        long long pries = daug;
        long long ats = daug;
        bool kur = 1;
        int nutraukti = 0;
        while(de<unikalus.size() && ka<unikalus.size() && de >=0 && ka >= 0)
        {
            //cout << k << ' ' << d << endl;
            long long atstumas = skaiciuok_keliu_suma(unikalus[ka], unikalus[de]);
            if(atstumas < pries)
            {
                pries = atstumas;
                ats = min(ats, atstumas);
                nutraukti = 0;
            }
            else
            {
                nutraukti++;
                pries = daug;
                if(kur)
                {
                    de--;
                    kur = 0;
                }
                else
                {
                    ka--;
                    kur = 1;
                }

            }
            if(kur) de++;
            else ka++;
            if(nutraukti > 5) break;
        }
        cout << ats;
    }
    return 0;
}

Compilation message

bridge.cpp: In function 'long long int skaiciuok_keliu_suma(int, int)':
bridge.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int i = 0; i<reikalingi.size(); i++)
      |                            ~^~~~~~~~~~~~~~~~~~
bridge.cpp:40:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int f = 0; f<reikalingi.size(); f++)
      |                            ~^~~~~~~~~~~~~~~~~~
bridge.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i<nereikalingi.size(); i++)
      |                    ~^~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:109:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while(de<unikalus.size() && ka<unikalus.size() && de >=0 && ka >= 0)
      |               ~~^~~~~~~~~~~~~~~~
bridge.cpp:109:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while(de<unikalus.size() && ka<unikalus.size() && de >=0 && ka >= 0)
      |                                     ~~^~~~~~~~~~~~~~~~
bridge.cpp:61:15: warning: unused variable 'A_puse' [-Wunused-variable]
   61 |     long long A_puse = 0;
      |               ^~~~~~
bridge.cpp:62:15: warning: unused variable 'B_puse' [-Wunused-variable]
   62 |     long long B_puse = 0;
      |               ^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 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 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.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 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 516 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 12 ms 3436 KB Output is correct
13 Correct 98 ms 13176 KB Output is correct
14 Correct 33 ms 3524 KB Output is correct
15 Correct 46 ms 7880 KB Output is correct
16 Correct 16 ms 3420 KB Output is correct
17 Correct 54 ms 13244 KB Output is correct
18 Correct 62 ms 13232 KB Output is correct
19 Correct 66 ms 12860 KB Output is correct
20 Correct 15 ms 3392 KB Output is correct
21 Correct 56 ms 13384 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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