oj.uz

Submission #1040211

# Submission time Handle Problem Language Result Execution time Memory
1040211 2024-07-31T18:32:39 Z Zicrus Sorting (IOI15_sorting) C++17
100 / 100
 143 ms 29780 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++;
                id1 = N;
                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: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:65:20: warning: declaration of 'id1' shadows a previous local [-Wshadow]
   65 |                 ll id1 = revS[firstOut];
      |                    ^~~
sorting.cpp:43:12: note: shadowed declaration is here
   43 |         ll id1 = -1;
      |            ^~~
sorting.cpp:71:26: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
   71 |                 P[res] = id1;
      |                          ^~~
sorting.cpp:72:26: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
   72 |                 Q[res] = id2;
      |                          ^~~
sorting.cpp:76:12: warning: declaration of 'ooo' shadows a previous local [-Wshadow]
   76 |         ll ooo = 0;
      |            ^~~
sorting.cpp:14:8: note: shadowed declaration is here
   14 |     ll ooo = 0;
      |        ^~~
sorting.cpp:90:9: warning: conversion from 'll' {aka 'long int'} to 'int' may change value [-Wconversion]
   90 |  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[]) {
      |                                   ~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 5 ms 11356 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 5 ms 11196 KB Output is correct
6 Correct 5 ms 11352 KB Output is correct
7 Correct 5 ms 11324 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 5 ms 11356 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 5 ms 11196 KB Output is correct
6 Correct 5 ms 11352 KB Output is correct
7 Correct 5 ms 11324 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 11356 KB Output is correct
11 Correct 5 ms 11396 KB Output is correct
12 Correct 5 ms 11356 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11356 KB Output is correct
2 Correct 6 ms 11356 KB Output is correct
3 Correct 6 ms 11356 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 5 ms 11356 KB Output is correct
6 Correct 5 ms 11352 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 5 ms 11356 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 5 ms 11196 KB Output is correct
6 Correct 5 ms 11352 KB Output is correct
7 Correct 5 ms 11324 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 11356 KB Output is correct
11 Correct 5 ms 11396 KB Output is correct
12 Correct 5 ms 11356 KB Output is correct
13 Correct 5 ms 11356 KB Output is correct
14 Correct 6 ms 11356 KB Output is correct
15 Correct 6 ms 11356 KB Output is correct
16 Correct 5 ms 11356 KB Output is correct
17 Correct 5 ms 11356 KB Output is correct
18 Correct 5 ms 11352 KB Output is correct
19 Correct 5 ms 11356 KB Output is correct
20 Correct 5 ms 11240 KB Output is correct
21 Correct 5 ms 11632 KB Output is correct
22 Correct 5 ms 11668 KB Output is correct
23 Correct 5 ms 11452 KB Output is correct
24 Correct 5 ms 11612 KB Output is correct
25 Correct 6 ms 11536 KB Output is correct
26 Correct 6 ms 11444 KB Output is correct
27 Correct 5 ms 11612 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 5 ms 11508 KB Output is correct
3 Correct 6 ms 11516 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 5 ms 11356 KB Output is correct
6 Correct 5 ms 11396 KB Output is correct
7 Correct 6 ms 11356 KB Output is correct
8 Correct 5 ms 11500 KB Output is correct
9 Correct 6 ms 11532 KB Output is correct
10 Correct 5 ms 11396 KB Output is correct
11 Correct 5 ms 11356 KB Output is correct
12 Correct 6 ms 11524 KB Output is correct
13 Correct 5 ms 11456 KB Output is correct
14 Correct 5 ms 11356 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 5 ms 11508 KB Output is correct
3 Correct 6 ms 11516 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 5 ms 11356 KB Output is correct
6 Correct 5 ms 11396 KB Output is correct
7 Correct 6 ms 11356 KB Output is correct
8 Correct 5 ms 11500 KB Output is correct
9 Correct 6 ms 11532 KB Output is correct
10 Correct 5 ms 11396 KB Output is correct
11 Correct 5 ms 11356 KB Output is correct
12 Correct 6 ms 11524 KB Output is correct
13 Correct 5 ms 11456 KB Output is correct
14 Correct 5 ms 11356 KB Output is correct
15 Correct 105 ms 27456 KB Output is correct
16 Correct 119 ms 27916 KB Output is correct
17 Correct 135 ms 28756 KB Output is correct
18 Correct 37 ms 24400 KB Output is correct
19 Correct 91 ms 27216 KB Output is correct
20 Correct 101 ms 28100 KB Output is correct
21 Correct 102 ms 27988 KB Output is correct
22 Correct 106 ms 24008 KB Output is correct
23 Correct 112 ms 29560 KB Output is correct
24 Correct 133 ms 29264 KB Output is correct
25 Correct 133 ms 29008 KB Output is correct
26 Correct 96 ms 27748 KB Output is correct
27 Correct 86 ms 27220 KB Output is correct
28 Correct 143 ms 29008 KB Output is correct
29 Correct 129 ms 28584 KB Output is correct
30 Correct 71 ms 26724 KB Output is correct
31 Correct 122 ms 28872 KB Output is correct
32 Correct 122 ms 28756 KB Output is correct
33 Correct 138 ms 29264 KB Output is correct
34 Correct 123 ms 29268 KB Output is correct
35 Correct 93 ms 26912 KB Output is correct
36 Correct 41 ms 26192 KB Output is correct
37 Correct 136 ms 29780 KB Output is correct
38 Correct 126 ms 28936 KB Output is correct
39 Correct 133 ms 29188 KB Output is correct