#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)
{
cout << skaiciuok_keliu_suma(medianai[medianai.size()/2], -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 k = 0, d = 1;
long long pries = daug;
long long ats = daug;
bool kur = 1;
int nutraukti = 0;
while(d<unikalus.size() && k<unikalus.size() && d >=0 && k >= 0)
{
//cout << k << ' ' << d << endl;
long long atstumas = skaiciuok_keliu_suma(unikalus[k], unikalus[d]);
if(atstumas < pries)
{
pries = atstumas;
ats = min(ats, atstumas);
nutraukti = 0;
}
else
{
nutraukti++;
pries = daug;
if(kur)
{
d--;
kur = 0;
}
else
{
k--;
kur = 1;
}
}
if(kur) d++;
else k++;
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:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while(d<unikalus.size() && k<unikalus.size() && d >=0 && k >= 0)
| ~^~~~~~~~~~~~~~~~
bridge.cpp:108:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while(d<unikalus.size() && k<unikalus.size() && d >=0 && k >= 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;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
