/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include "sorting.h"
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
if (res > val) { res = val; return true; } return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int Nx = 2e5 + 100;
ii b[Nx];
int a[Nx];
int n , m;
int cnt = 0;
vector <ii> p;
void calc(int l , int r)
{
if (l > r) return ;
if (l == r) return ;
int mid = (l + r) >> 1;
// cout << l << " " << r << " " << mid << "\n";
int j = mid + 1;
for (int i = l ; i <= mid ; i++)
if (a[i] > mid)
{
for (; j <= n ; j++) if (a[j] <= mid) break;
p.push_back(C(i,j));
// cout << i << " " << j << " " << mid << " " << a[i] << " " << a[j] << "\n";
swap(a[i],a[j]);
}
calc(l,mid);
calc(mid+1,r);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
m = M;
if (n == 1) return 0;
for (int i = 0 ; i < n ; i++) a[i] = S[i];
for (int i = 0 ; i < m ; i++)
{
b[i] = C(X[i],Y[i]);
}
// if (X[0] == 0 && Y[0] == 1){
// swap(a[0],a[1]);
// for (int i = 0 ; i < n ; i++) if (a[i] == 0)
// {
// swap(a[i],a[0]);
// p.push_back(C(0,i));
// }
// swap(a[0],a[1]);
// for (int i = 0 ; i < n ; i++) if (a[i] == 1)
// {
// int x = 0;
// if (a[x] == 0) x = 1;
// swap(a[i],a[x]);
// p.push_back(C(x,i));
// }
// // for (int i = 0 ; i < n ; i++) cout << a[i] << " ";
// // cout << "\n";
// calc(2,n - 1);
// }
//else
calc(0,n - 1);
while (p.size() < m) p.push_back(C(0,0));
// for (int i = 0 ; i < m ; i++)
// {
// swap(S[b[i].fi],S[b[i].se]);
// swap(S[p[i].fi],S[p[i].se]);
// // cout << b[i].fi << " " << b[i].se << "\n";
// // for (int j = 0 ; j < n ; j++) cout << S[j] << " ";
// // cout << "\n";
// }
// if (S[0] == 1)
// {
// p[m - 1] = (C(0,1));
// swap(S[0],S[1]);
// }
// for (ii v : p) cout << v.fi << " " << v.se << "\n";
// for (int i = 0 ; i < n ; i++) cout << S[i] << " ";
for (int i = 0 ; i < m ; i++) P[i] = p[i].fi,Q[i] = p[i].se;
return m;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(NULL); cout.tie(NULL);
// if(fopen(TASK".inp", "r")){
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
// }
// int x[Nx] , y[Nx] , s[Nx] , t[Nx] , q[Nx];
// int r , o;
// cin >> r >> o;
// for (int i = 0 ; i < r ; i++) cin >> s[i];
// for (int i = 0 ; i < o ; i++)
// cin >> x[i] >> y[i];
// findSwapPairs(r,s,o,x,y,t,q);
// return 0;
// }
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:102:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
102 | while (p.size() < m) p.push_back(C(0,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 |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
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 |
- |
| # |
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 |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
