#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
priority_queue<pair<int,int>>pq;
int n = N;
vector<int>cnt(N,0);
for(int i = 0 ; i < N ; i++) {
cnt[X[i]]++,cnt[Y[i]]++;
}
vector<int>pos(n),need(n);
for(int i = 0 ; i < n ; i++) {
pq.push({-cnt[i],i});
pos[S[i]] = i;
need[i] = S[i];
}
int d=0;
auto done = [&] (void) -> bool {
for(int i = 0 ; i < n ; i++)
if(S[i] != i) return false;
return true;
};
for(int i = 0 ; i < n ; i++) {
if(done()) return d;
swap(S[X[i]],S[Y[i]]);
cnt[X[i]]--,cnt[Y[i]]--;
swap(pos[S[X[i]]],pos[S[Y[i]]]);
swap(need[X[i]],need[Y[i]]);
pq.push({-cnt[X[i]],X[i]});
pq.push({-cnt[Y[i]],Y[i]});
while(pq.top().first != -cnt[pq.top().second])
pq.pop();
if(pos[pq.top().second] != pq.top().second)
P[d++] = (min(pos[pq.top().second],pq.top().second)),Q[d] = (max(pos[pq.top().second],pq.top().second)),
swap(pos[pq.top().second],pos[need[pq.top().second]]), swap(need[pq.top().second],need[pos[pq.top().second]]);
pq.pop();
}
return d;
}
/*
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//#include "sorting.h"
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main()
{
_inputFile = fopen("sorting1.in", "r");
_outputFile = fopen("sorting1_out.txt", "w");
int N, M;
N = _readInt();
int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
for (int i = 0; i < N; ++i)
S[i] = _readInt();
M = _readInt();
int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
for (int i = 0; i < M; ++i) {
X[i] = _readInt();
Y[i] = _readInt();
}
int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
int ans = findSwapPairs(N, S, M, X, Y, P, Q);
fprintf(_outputFile, "%d\n", ans);
for (int i = 0; i < ans; ++i)
fprintf(_outputFile, "%d %d\n", P[i], Q[i]);
return 0;
}
*/
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:5:39: warning: unused parameter 'M' [-Wunused-parameter]
5 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
