| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 419227 |
2021-06-06T14:59:16 Z |
Mounir |
Sorting (IOI15_sorting) |
C++14 |
|
2 ms |
332 KB |
#include "sorting.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N_VALS = 1e6;
int nVals, nTours;
vector<int> vals, tmp;
vector<pii> modifs;
bool vu[N_VALS];
int nCycles(){
for (int ind = 0; ind < nVals; ++ind)
vu[ind] = false;
int nb = 0;
//cout << "BEGIN" << endl;
for (int depart = 0; depart < nVals; ++depart){
if (!vu[depart]){
nb++;
vu[depart] = true;
int noeud = vals[depart];
while (noeud != depart){
vu[noeud] = true;
noeud = vals[noeud];
}
}
}
//cout << "END" << endl;
return nb;
}
void faireSwaps(int borneMax){
for (int ind = 0; ind < nVals; ++ind)
vals[ind] = tmp[ind];
for (int ind = 1; ind < borneMax; ++ind)
swap(vals[modifs[ind].x], vals[modifs[ind].y]);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
//initialisation.
nVals = N, nTours = M;
vals.resize(nVals), tmp.resize(nVals);
for (int ind = 0; ind < nVals; ++ind)
vals[ind] = tmp[ind] = S[ind];
modifs.resize(nTours + 1);
for (int ind = 0; ind < nTours; ++ind)
modifs[ind + 1] = {X[ind], Y[ind]};
//Dichotomie pour trouver R.
int gauche = 0, droite = nTours + 1; //vu que la fin est exclue
while (droite > gauche){
int milieu = (droite + gauche)/2;
faireSwaps(milieu);
// cout << "m " << milieu << " " << gauche << " " << droite << endl;
/* cout << "MILIEU " << milieu << " " << nCycles() << endl;
for (int val : vals)
cout << val << " ";
cout << endl;
*/
if (milieu >= nVals - nCycles())
droite = milieu;
else
gauche = milieu + 1;
}
int res = gauche - 1;
faireSwaps(res);
int nb = 0;
for (int ind = 0; ind < nVals; ++ind){
while (vals[ind] != ind){
P[nb] = ind;
Q[nb] = vals[ind];
swap(vals[ind], vals[vals[ind]]);
nb++;
}
}
while (nb < res){
P[nb] = Q[nb] = 0;
nb++;
}
/*
for (int ind = 0; ind < res; ++ind)
cout << P[ind] << " " << Q[ind] << endl;
*/
vector<int> permutation(nVals);
for (int ind = 0; ind < nVals; ++ind)
permutation[ind] = ind;
for (int iModif = res; iModif >= 2; --iModif){
swap(vals[permutation[modifs[iModif].x]], vals[permutation[modifs[iModif].y]]);
swap(permutation[modifs[iModif].x], permutation[modifs[iModif].y]);
P[iModif] = vals[P[iModif]];
Q[iModif] = vals[Q[iModif]];
}
/*
for (int ind = 0; ind < res; ++ind){
P[ind] = P[ind + 1];
Q[ind] = Q[ind + 1];
}
*/
/*
cout << "SALUT\n";
for (int ind = 0; ind < res; ++ind){
cout << "TOUR\n";
cout << X[ind] << " " << Y[ind] << endl;
cout << P[ind] << " " << Q[ind] << endl;
swap(vals[X[ind]], vals[Y[ind]]);
swap(vals[P[ind]], vals[Q[ind]]);
for (int val : vals)
cout << val << " ";
cout << endl;
}
*/
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
204 KB |
MODEL SOLUTION IS WRONG |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
204 KB |
MODEL SOLUTION IS WRONG |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
204 KB |
MODEL SOLUTION IS WRONG |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
204 KB |
MODEL SOLUTION IS WRONG |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
