oj.uz

Submission #408861

# Submission time Handle Problem Language Result Execution time Memory
408861 2021-05-19T18:16:21 Z cpp219 Sorting (IOI15_sorting) C++14
20 / 100
 2 ms 588 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <sorting.h>
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<ll> v,pos;
vector<LL> oper,ans;
ll n,m,id1[N],a[N],b[N],id2[N];

bool chk(ll mid){
    for (ll i = 0;i < n;i++) a[i] = b[i] = v[i]; ans.clear();
    for (ll i = 0;i < mid;i++){
        ll x = oper[i].fs,y = oper[i].sc;
        swap(a[x],a[y]);
    }
    for (ll i = 0;i < n;i++) id1[a[i]] = i,id2[b[i]] = i;
    ll j = 0;
    for (ll i = 0;i < mid;i++){
        ll x = oper[i].fs,y = oper[i].sc;
        swap(id2[b[x]],id2[b[y]]);
        while (j < n&&a[j] == j) j++;
        if (j == n) ans.push_back({0,0});
        else{
            ans.push_back({id2[j],id2[a[j]]});
            swap(b[id2[j]],b[id2[a[j]]]);
            swap(id2[j],id2[a[j]]);
            id1[a[j]] = id1[j]; swap(a[j],a[id1[j]]);
            id1[j] = j;
        }
    }
    for (ll i = 0;i < n - 1;i++) if (a[i] > a[i + 1]) return 0;
    return 1;
}

ll findSwapPairs(ll num,ll S[],ll M,ll X[],ll Y[],ll P[],ll Q[]){
    n = num; m = M;
    for (ll i = 0;i < n;i++) v.push_back(S[i]);
    for (ll i = 0;i < M;i++) oper.push_back({X[i],Y[i]});
    ll l,mid,h;
    l = 0; h = m;
    //chk(3); exit(0);
    while(l <= h){
        mid = (l + h)/2;
        if (chk(mid)) h = mid - 1;
        else l = mid + 1;
    }
    chk(l); //cout<<ans.size(); exit(0);
    while(ans.size() < l) ans.push_back({0,0});
    for (ll i = 0;i < ans.size();i++) P[i] = ans[i].fs,Q[i] = ans[i].sc;
    return l;
}

Compilation message

sorting.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
sorting.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
sorting.cpp: In function 'bool chk(int)':
sorting.cpp:20:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   20 |     for (ll i = 0;i < n;i++) a[i] = b[i] = v[i]; ans.clear();
      |     ^~~
sorting.cpp:20:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   20 |     for (ll i = 0;i < n;i++) a[i] = b[i] = v[i]; ans.clear();
      |                                                  ^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:57:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     while(ans.size() < l) ans.push_back({0,0});
      |           ~~~~~~~~~~~^~~
sorting.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (ll i = 0;i < ans.size();i++) P[i] = ans[i].fs,Q[i] = ans[i].sc;
      |                   ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -