oj.uz

Submission #251167

# Submission time Handle Problem Language Result Execution time Memory
251167 2020-07-20T13:13:34 Z anakib1 Sorting (IOI15_sorting) C++17
100 / 100
 182 ms 29816 KB 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define sz(a) (int)(a.size())
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define problem ""

template<typename A, typename B, typename C>
struct triple{
    A X;
    B Y;
    C Z;
    triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0){
    return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b){
    if (a.X != b.X)
        return a.X < b.X;
    if (a.Y != b.Y)
        return a.Y < b.Y;
    return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p){
    ofs << "( " << p.F << " , " << p.S << " )";
    return ofs;
}
template<typename T>
void print(T a){
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
template<typename T>
T max(T a, T b, T c){
    return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c){
    return min(a, min(b, c));
}
template<typename T, typename D>
D min(T a){
    return *min_element(all(a));
}
template<typename T, typename D>
D max(T a){
    return *max_element(all(a));
}
struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
int n, m;
#define mxn (int)(6e5 + 1)
int s[mxn], a[mxn], x[mxn], y[mxn], p[mxn], q[mxn], pos[mxn], sa[mxn], sb[mxn];
int pp;
int ans;
void make(int now){
    while(pp <= now) {swap(s[x[pp]], s[y[pp]]); pp++;}
    while(pp > now + 1) {pp--; swap(s[x[pp]], s[y[pp]]);}
}
void SWAP(int i, int j) {
  int ii = pos[a[i]];
  int jj = pos[a[j]];
  pos[a[i]] = jj;
  pos[a[j]] = ii;
  swap(a[i], a[j]);
}
bool ok(int x){
    int c = 0;
    rngi(i, n)pos[s[i]] = i, a[i]=s[i];
    rngi(i, n) if(a[i] != i) {
        sa[c] = i; sb[c] = a[i];
        c++;
        SWAP(i, pos[i]);
    }
    for(int i = c; i < x;i++) sa[i]=sb[i]=0;
    return c <= x;
}
void asn(){
    for(int i = ans - 1; i >= 0; i--) {
      p[i] = pos[sa[i]], q[i] = pos[sb[i]];
      SWAP(p[i], q[i]);
      SWAP(x[i + 1], y[i + 1]);
    }
}
int findSwapPairs(int N, int ss[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N, m = M;
    rngi(i, n) s[i]=ss[i];
    for(int i = 1; i <= m; i++) x[i]=X[i - 1], y[i]= Y[i-1];
    int l = 0, r= M;
    while(l <= r){
        int mid = l +r >> 1;
        make(mid);
        if(ok(mid)) { ans = mid, r = mid - 1;} else l = mid + 1;
    }
    make(ans);
    ok(ans);
    asn();
    rngi(i, ans) P[i]=p[i], Q[i]= q[i];
    return ans;
}

Compilation message

sorting.cpp: In function 'bool ok(int)':
sorting.cpp:128:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 bool ok(int x){
              ^
sorting.cpp:114:21: note: shadowed declaration is here
 int s[mxn], a[mxn], x[mxn], y[mxn], p[mxn], q[mxn], pos[mxn], sa[mxn], sb[mxn];
                     ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:152:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l +r >> 1;
                   ~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 1 ms 768 KB Output is correct
23 Correct 1 ms 768 KB Output is correct
24 Correct 1 ms 640 KB Output is correct
25 Correct 1 ms 640 KB Output is correct
26 Correct 1 ms 640 KB Output is correct
27 Correct 1 ms 640 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 142 ms 18680 KB Output is correct
16 Correct 156 ms 27004 KB Output is correct
17 Correct 172 ms 28408 KB Output is correct
18 Correct 79 ms 22136 KB Output is correct
19 Correct 132 ms 26104 KB Output is correct
20 Correct 148 ms 27000 KB Output is correct
21 Correct 177 ms 27000 KB Output is correct
22 Correct 143 ms 23800 KB Output is correct
23 Correct 165 ms 29560 KB Output is correct
24 Correct 177 ms 29048 KB Output is correct
25 Correct 174 ms 28664 KB Output is correct
26 Correct 143 ms 27000 KB Output is correct
27 Correct 127 ms 26104 KB Output is correct
28 Correct 156 ms 28796 KB Output is correct
29 Correct 160 ms 28024 KB Output is correct
30 Correct 107 ms 25288 KB Output is correct
31 Correct 169 ms 28664 KB Output is correct
32 Correct 159 ms 28536 KB Output is correct
33 Correct 162 ms 28920 KB Output is correct
34 Correct 168 ms 28960 KB Output is correct
35 Correct 129 ms 25848 KB Output is correct
36 Correct 66 ms 23800 KB Output is correct
37 Correct 182 ms 29816 KB Output is correct
38 Correct 171 ms 28540 KB Output is correct
39 Correct 166 ms 28792 KB Output is correct