oj.uz

Submission #344277

# Submission time Handle Problem Language Result Execution time Memory
344277 2021-01-05T11:20:38 Z AmineWeslati Sorting (IOI15_sorting) C++14
100 / 100
 360 ms 27720 KB 
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
#ifndef LOCAL
#include "sorting.h"
#endif
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int N,S[MX],X[MX],Y[MX];
vi plate(MX),pos(MX),cur(MX),final(MX),apple(MX);
vpi vec;

bool check(int n){
    vec.clear();
    //initialize containers
    FOR(i,0,N){
        plate[i]=i;
        pos[i]=i;
        apple[i]=S[i];
        cur[apple[i]]=i;
    }
    vi v(N); FOR(i,0,N) v[i]=i;
    FOR(i,0,n) swap(v[X[i]],v[Y[i]]);
    FOR(i,0,N) final[i]=v[i];

    //FOR(i,0,N) cout << final[i] << ' '; cout << endl;
    
    //compute
    int cnt=0; //nb of operations needed
    FOR(i,0,N) if(final[i]!=cur[i]){
        //First plays
        int l=X[cnt],r=Y[cnt];
        //dbgs(l,r)
        swap(plate[l],plate[r]);
        swap(pos[plate[l]],pos[plate[r]]);

        //Sec plays
        vec.eb(pos[cur[i]],pos[final[i]]);
        int app=apple[final[i]];
        swap(apple[cur[i]],apple[final[i]]);
        swap(cur[i],cur[app]);
        assert(cur[i]==final[i]);

        cnt++;
    }
    if(cnt>n) return false;
    FOR(i,cnt,n) vec.eb(0,0);
    return true;
}

int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
    ::N=N;
    FOR(i,0,N) S[i]=s[i];
    FOR(i,0,N) X[i]=x[i],Y[i]=y[i];

    int l=0,r=N-1;
    vpi ans;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)){
            r=m-1;
            ans.assign(all(vec));
        }
        else l=m+1;
    }
    FOR(i,0,sz(ans)){
        P[i]=ans[i].fi,Q[i]=ans[i].se;
        swap(s[x[i]],s[y[i]]);
        swap(s[P[i]],s[Q[i]]);
    }
    //FOR(i,0,N) cout << s[i] << ' '; cout << endl;
    return sz(ans);
}

#ifdef LOCAL
int main() {
    boost; IO();

    int N; cin>>N;
    int s[N]; FOR(i,0,N) s[i]=i;
    random_shuffle(s,s+N);
    //FOR(i,0,N) cout << s[i] << ' '; cout << endl;

    int M=3*N;
    int p[M],q[M],x[M],y[M];
    FOR(i,0,M) x[i]=random(0,N-1),y[i]=random(0,N-1);
    //FOR(i,0,M) cout << x[i] << ' ' << y[i] << endl;

    cout << findSwapPairs(N,s,M,x,y,p,q) << endl;

    return 0;
}
#endif

/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:110:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  110 | int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
      |                                                                            ^
sorting.cpp:68:5: note: shadowed declaration is here
   68 | int N,S[MX],X[MX],Y[MX];
      |     ^
sorting.cpp:110:39: warning: unused parameter 'M' [-Wunused-parameter]
  110 | int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
      |                                   ~~~~^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4204 KB Output is correct
2 Correct 4 ms 4352 KB Output is correct
3 Correct 5 ms 4332 KB Output is correct
4 Correct 5 ms 4332 KB Output is correct
5 Correct 4 ms 4332 KB Output is correct
6 Correct 4 ms 4204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4204 KB Output is correct
4 Correct 4 ms 4204 KB Output is correct
5 Correct 4 ms 4320 KB Output is correct
6 Correct 4 ms 4204 KB Output is correct
7 Correct 4 ms 4204 KB Output is correct
8 Correct 5 ms 4204 KB Output is correct
9 Correct 4 ms 4204 KB Output is correct
10 Correct 4 ms 4332 KB Output is correct
11 Correct 4 ms 4332 KB Output is correct
12 Correct 4 ms 4204 KB Output is correct
13 Correct 4 ms 4204 KB Output is correct
14 Correct 4 ms 4352 KB Output is correct
15 Correct 5 ms 4332 KB Output is correct
16 Correct 5 ms 4332 KB Output is correct
17 Correct 4 ms 4332 KB Output is correct
18 Correct 4 ms 4204 KB Output is correct
19 Correct 4 ms 4204 KB Output is correct
20 Correct 4 ms 4204 KB Output is correct
21 Correct 4 ms 4460 KB Output is correct
22 Correct 4 ms 4460 KB Output is correct
23 Correct 4 ms 4460 KB Output is correct
24 Correct 4 ms 4460 KB Output is correct
25 Correct 4 ms 4460 KB Output is correct
26 Correct 4 ms 4492 KB Output is correct
27 Correct 5 ms 4460 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4460 KB Output is correct
2 Correct 5 ms 4460 KB Output is correct
3 Correct 5 ms 4460 KB Output is correct
4 Correct 4 ms 4460 KB Output is correct
5 Correct 4 ms 4460 KB Output is correct
6 Correct 5 ms 4460 KB Output is correct
7 Correct 6 ms 4460 KB Output is correct
8 Correct 6 ms 4460 KB Output is correct
9 Correct 7 ms 4460 KB Output is correct
10 Correct 5 ms 4460 KB Output is correct
11 Correct 6 ms 4460 KB Output is correct
12 Correct 5 ms 4460 KB Output is correct
13 Correct 7 ms 4460 KB Output is correct
14 Correct 5 ms 4460 KB Output is correct
15 Correct 198 ms 17216 KB Output is correct
16 Correct 227 ms 25100 KB Output is correct
17 Correct 336 ms 26268 KB Output is correct
18 Correct 88 ms 21904 KB Output is correct
19 Correct 226 ms 23524 KB Output is correct
20 Correct 242 ms 25176 KB Output is correct
21 Correct 244 ms 25144 KB Output is correct
22 Correct 196 ms 21632 KB Output is correct
23 Correct 224 ms 27348 KB Output is correct
24 Correct 350 ms 26788 KB Output is correct
25 Correct 324 ms 26512 KB Output is correct
26 Correct 222 ms 25804 KB Output is correct
27 Correct 205 ms 23776 KB Output is correct
28 Correct 268 ms 26648 KB Output is correct
29 Correct 303 ms 25920 KB Output is correct
30 Correct 154 ms 23388 KB Output is correct
31 Correct 296 ms 26624 KB Output is correct
32 Correct 225 ms 26388 KB Output is correct
33 Correct 360 ms 26872 KB Output is correct
34 Correct 243 ms 26752 KB Output is correct
35 Correct 219 ms 23232 KB Output is correct
36 Correct 75 ms 23000 KB Output is correct
37 Correct 346 ms 27720 KB Output is correct
38 Correct 331 ms 26512 KB Output is correct
39 Correct 345 ms 26752 KB Output is correct