| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1040207 |
2024-07-31T18:30:10 Z |
Zicrus |
Sorting (IOI15_sorting) |
C++17 |
|
6 ms |
11428 KB |
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
typedef int_fast32_t ll;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P1[], int Q1[]) {
ll h[200000];
for (ll i = 0; i < N; i++) h[i] = S[i];
ll ooo = 0;
for (ll i = 0; i < N; i++) {
if (h[i] != i) ooo++;
}
if (ooo == 0) return 0;
int P[200000], Q[200000];
ll revH[200000];
for (int i = 0; i < N; i++) {
revH[h[i]] = i;
}
ll res1 =0;
ll low = 1, high = N;
ll s[200000], order[200000], revOrd[200000], revS[200000];
while (low < high) {
ll g = (low + high) / 2;
ll res = 0;
memcpy(s, h, N * sizeof(ll));
memcpy(order, h, N * sizeof(ll));
memcpy(revOrd, revH, N * sizeof(ll));
memcpy(revS, revH, N * sizeof(ll));
for (ll j = 0; j < g; j++) {
swap(order[X[j]], order[Y[j]]);
swap(revOrd[order[X[j]]], revOrd[order[Y[j]]]);
}
ll id1 = -1;
for (ll i = 0; i < g; i++) {
swap(s[X[i]], s[Y[i]]);
swap(revS[s[X[i]]], revS[s[Y[i]]]);
int firstOut = -1, id = -1;
for (int j = id1+1; j < N; j++) {
if (order[j] != j) {
firstOut = order[id = j];
break;
}
}
id1 = id;
if (firstOut == -1) {
P[res] = Q[res] = 0;
res++;
break;
}
else {
ll iter = revOrd[id];
ll v = order[iter];
ll id1 = revS[firstOut];
ll id2 = revS[v];
swap(s[id1], s[id2]);
swap(revS[s[id1]], revS[s[id2]]);
swap(order[iter], order[id]);
swap(revOrd[order[iter]], revOrd[order[id]]);
P[res] = id1;
Q[res] = id2;
res++;
}
}
ll ooo = 0;
for (ll i = 0; i < N; i++) {
if (s[i] != i) ooo++;
}
if (ooo == 0) {
res1 = res;
high = res;
memcpy(P1, P, res * sizeof(int));
memcpy(Q1, Q, res * sizeof(int));
}else {
low = g+1;
}
}
return res1;
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:48:29: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
48 | for (int j = id1+1; j < N; j++) {
| ~~~^~
sorting.cpp:50:44: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
50 | firstOut = order[id = j];
| ~~~~~~~~~~~~^
sorting.cpp:64:20: warning: declaration of 'id1' shadows a previous local [-Wshadow]
64 | ll id1 = revS[firstOut];
| ^~~
sorting.cpp:43:12: note: shadowed declaration is here
43 | ll id1 = -1;
| ^~~
sorting.cpp:70:26: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
70 | P[res] = id1;
| ^~~
sorting.cpp:71:26: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
71 | Q[res] = id2;
| ^~~
sorting.cpp:75:12: warning: declaration of 'ooo' shadows a previous local [-Wshadow]
75 | ll ooo = 0;
| ^~~
sorting.cpp:14:8: note: shadowed declaration is here
14 | ll ooo = 0;
| ^~~
sorting.cpp:89:9: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
89 | return res1;
| ^~~~
sorting.cpp:10:39: warning: unused parameter 'M' [-Wunused-parameter]
10 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P1[], int Q1[]) {
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
4 ms |
11376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
11344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 6 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
5 ms |
11352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
4 ms |
11376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
11344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 6 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
5 ms |
11352 KB |
Output is correct |
| 8 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 9 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
5 ms |
11428 KB |
Output is correct |
| 11 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 12 |
Correct |
6 ms |
11356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11280 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
4 ms |
11376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
11344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 6 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
5 ms |
11352 KB |
Output is correct |
| 8 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 9 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
5 ms |
11428 KB |
Output is correct |
| 11 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 12 |
Correct |
6 ms |
11356 KB |
Output is correct |
| 13 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 14 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 15 |
Incorrect |
5 ms |
11280 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
