| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1040203 |
2024-07-31T18:26:30 Z |
Zicrus |
Sorting (IOI15_sorting) |
C++17 |
|
14 ms |
22884 KB |
#pragma GCC optimize("Ofast")
#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];
int P[200000], Q[200000];
ll revH[200000];
for (int i = 0; i < N; i++) {
revH[h[i]] = i;
}
ll res1 =0;
ll low = 0, high = 200000;
ll s[200000], order[200000], revOrd[200000], revS[200000];
while (low < high) {
ll g = (low + high) / 2;
ll res = 0;
memcpy(s, h, 200000 * sizeof(ll));
memcpy(order, h, 200000 * sizeof(ll));
memcpy(revOrd, revH, 200000 * sizeof(ll));
memcpy(revS, revH, 200000 * 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++;
continue;
}
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:42:29: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
42 | for (int j = id1+1; j < N; j++) {
| ~~~^~
sorting.cpp:44:44: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
44 | firstOut = order[id = j];
| ~~~~~~~~~~~~^
sorting.cpp:58:20: warning: declaration of 'id1' shadows a previous local [-Wshadow]
58 | ll id1 = revS[firstOut];
| ^~~
sorting.cpp:37:12: note: shadowed declaration is here
37 | ll id1 = -1;
| ^~~
sorting.cpp:64:26: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
64 | P[res] = id1;
| ^~~
sorting.cpp:65:26: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
65 | Q[res] = id2;
| ^~~
sorting.cpp:83:9: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
83 | 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 |
Runtime error |
12 ms |
22712 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
22712 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
22620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
22712 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
22884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
22884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
