#include <bits/stdc++.h>
using namespace std;
#define endl "\n";
pair<int, vector<int>> binarySearch(vector<pair<string, int>> arr, int l, int r, string x, vector<pair<string, int>> lista)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid].first == x){
int res = 0;
int odstep = 0;
vector<int> listaRes;
while(mid - odstep > 0 && mid + odstep < arr.size() - 1){
odstep++;
if(arr[mid - odstep].first == x && lista[arr[mid - odstep].second].second != -2){
res++;
listaRes.push_back(arr[mid - odstep].second);
//cout << arr[mid - odstep].first << " = " << x << endl;
}
if(arr[mid + odstep].first == x && lista[arr[mid + odstep].second].second != -2){
res++;
listaRes.push_back(arr[mid + odstep].second);
//cout << arr[mid + odstep].first << " = " << x << endl;
}
else if(arr[mid - odstep].first != x && arr[mid - odstep].first != x) break;
}
if(lista[arr[mid].second].second != -2){
//cout << arr[mid].first << " = " << x << endl;
listaRes.push_back(arr[mid].second);
res++;
}
return {res, listaRes};
}
if (arr[mid].first[0] > x[0] || arr[mid].first[1] > x[1]){
return binarySearch(arr, l, mid - 1, x, lista);
}
return binarySearch(arr, mid + 1, r, x, lista);
}
return {0, {}};
}
void solve(){
int n, res = 0;
string jeden, dwa;
cin >> n;
vector<pair<string, int>> lista(n, {"", 0});
for(int i = 0; i < n; i++){
cin >> jeden >> dwa;
lista[i].first += jeden + dwa;
}
vector<pair<string, int>> gora, dol, prawo, lewo;
int i = 0;
for(auto napis : lista){
string uGury(1, napis.first[0]);
uGury += napis.first[1];
gora.push_back({uGury,i});
string uDole(1, napis.first[2]);
uDole += napis.first[3];
dol.push_back({uDole,i});
string uPrawo(1, napis.first[1]);
uPrawo += napis.first[3];
prawo.push_back({uPrawo,i});
string uLewo(1, napis.first[0]);
uLewo += napis.first[2];
lewo.push_back({uLewo,i});
i++;
}
sort(dol.begin(), dol.end());
sort(lewo.begin(), lewo.end());
//for(auto el : dol) cout << el.second << " -> " << el.first << endl;
pair<int, vector<int>> dodatek;
for(auto &el : gora){
lista[el.second].second = -2;
dodatek = binarySearch(dol, 0, n / 2, el.first, lista);
res += dodatek.first;
if(dodatek.first){
for(auto indeks : dodatek.second){
lista[indeks].second = -1;
}
}
}
for(auto &el : prawo){
if(lista[el.second].second == 0){
dodatek = binarySearch(lewo, 0, n / 2, el.first, lista);
res += dodatek.first;
}
}
cout << res << endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
solve();
}
Compilation message
korteles.cpp: In function 'std::pair<int, std::vector<int> > binarySearch(std::vector<std::pair<std::__cxx11::basic_string<char>, int> >, int, int, std::string, std::vector<std::pair<std::__cxx11::basic_string<char>, int> >)':
korteles.cpp:13:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | while(mid - odstep > 0 && mid + odstep < arr.size() - 1){
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
508 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1088 ms |
74864 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
