/* [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]);
// swap(a[b[i].fi],a[b[i].se]);
}
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 (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 |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
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 |
1 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |