Submission #1134796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134796		t9unkubj	Sorting (IOI15_sorting)	C++20	0 / 100	1 ms	584 KiB

sorting

#include "sorting.h"
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct uf{
    vc<int>par;
    uf(int n):par(n,-1){}
    int root(int a){
        if(par[a]<0)return a;
        return par[a]=root(par[a]);
    }
    int merge(int a,int b){
        a=root(a),b=root(b);
        if(a==b)return 0;
        if(-par[a]<-par[b])swap(a,b);
        par[a]+=par[b];
        par[b]=a;
        return 1;
    }
};
vc<pair<int,int>>solve(int n,vc<int>s,int m,vc<int>x,vc<int>y){
    auto judge=[&](int wj){
        auto ns=s;
        rep(i,wj){
            swap(ns[x[i]],ns[y[i]]);
        }
        uf uf(n);
        rep(i,n){
            uf.merge(i,ns[i]);
        }
        int cnt=0;
        rep(i,n)if(i==uf.root(i))cnt++;
        if(n-cnt<=wj)return 1;
        else return 0;
    };
    int ac=m,wa=0;
    while(ac-wa>1){
        int wj=ac+wa>>1;
        if(judge(wj))ac=wj;
        else wa=wj;
    }
    
    auto build=[&](int ac){
        vc<pair<int,int>>ans;
        uf uf(n);
        auto ns=s;
        rep(i,ac){
            swap(ns[x[i]],ns[y[i]]);
        }
        rep(i,n)uf.merge(i,ns[i]);
        vvc<int>gs(n);
        rep(i,n){
            gs[uf.root(i)].push_back(i);
        }
        vc<int>inv(n);
        rep(i,n){
            inv[ns[i]]=i;
        }
        auto SWAP=[&](int a,int b){
            swap(inv[ns[a]],inv[ns[b]]);
            swap(ns[a],ns[b]);
        };

        rep(i,n){
            REP(j,1,gs[i].size()){
                ans.push_back({ns[gs[i][j]],gs[i][j]});
            }
        }
        while(ans.size()<ac)ans.push_back({0,0});
        vc<int>now(n);
        iota(all(now),0);
        vc<int>now_inv(n);
        rep(i,n)now_inv[i]=i;
        //i番目のりんごが載っている皿
        vc<int>now_on(n);
        iota(all(now_on),0);
        //i番目の皿が載せているリンゴ
        vc<int>inv_on=now_on;

        rep(i,n){
            now_on[s[i]]=i;
        }

        inv_on=s;
        rep(i,ac){
            swap(now[x[i]],now[y[i]]);
            swap(now_inv[now[x[i]]],now_inv[now[y[i]]]);     
            swap(now_on[ans[i].first],now_on[ans[i].second]);
            ans[i].first=now_inv[now_on[ans[i].first]];
            ans[i].second=now_inv[now_on[ans[i].second]];
        }
        return ans;
    };
    return build(ac);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    vc<int>s(N);
    vc<int>x(M),y(M);
    rep(i,N){
        s[i]=S[i];
    }
    rep(i,M){
        x[i]=X[i],y[i]=Y[i];
    }
    auto R=solve(N,s,M,x,y);
    rep(i,R.size()){
        P[i]=R[i].first;
        Q[i]=R[i].second;
    }
    return R.size();
}
#ifdef t9unkubj
namespace judge{
    void run(){
        int n;
        cin>>n;
        vc<int>s(n);
        rep(i,n)cin>>s[i];
        int m;
        cin>>m;
        vc<int>x(m),y(m);
        rep(i,m)cin>>x[i]>>y[i];
        auto R=(solve(n,s,m,x,y));
        dbg("DON"s);
        rep(i,R.size()){
            swap(s[x[i]],s[y[i]]);
            swap(s[R[i].first],s[R[i].second]);
        }
        dbg(s);
        dbg(R);
    }  
};
int main(){judge::run();}
#endif

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