Submission #408863

#	Time	Username	Problem	Language	Result	Execution time	Memory
408863		cpp219	Sorting (IOI15_sorting)	C++14	100 / 100	361 ms	30052 KiB

sorting

#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]]);
        swap(b[x],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 (stderr)

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:58: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]
   58 |     while(ans.size() < l) ans.push_back({0,0});
      |           ~~~~~~~~~~~^~~
sorting.cpp:59: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]
   59 |     for (ll i = 0;i < ans.size();i++) P[i] = ans[i].fs,Q[i] = ans[i].sc;
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26