AOJ2632 Dense Amidakuji

問題ページ

解法1

横棒の消去を無視すると周期 で同じ列に戻ってくる．ある横棒 を消す場合，その横棒の左端/右端にくる列が何列目なのか求め，その位置をswapする．左端/右端にくる列を求めるには，0列目/w-1列目に当たるまで上に戻るを繰り返すことで で求められる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll h, w, n;  
    cin >> h >> w >> n;  
    vector<PII> v(n);  
    REP(i, n) {  
        ll a, b;  
        cin >> a >> b;  
        a--, b--;  
        v[i] = {a, b};  
    }  
  
    auto func = [&](ll y, ll x) {  
        y %= 2*w;  
        while(y) {  
            ll tmp;  
            if((y+x)%2) tmp = min(y, w-x-1);  
            else tmp = -min(y,x);  
            x += tmp;  
            y -= abs(tmp);  
            if(y) y--;  
        }  
        return x;  
    };  
  
    sort(ALL(v));  
    vector<ll> x(w);  
    iota(ALL(x), 0);  
    dump(x);  
    REP(i, n) {  
        ll a = v[i].first, l = v[i].second, r = l+1;  
        swap(x[func(a, l)], x[func(a, r)]);  
        dump(a, l, r, x);  
    }  
    vector<ll> ans(w);  
    REP(i, w) ans[x[func(h,i)]] = i;  
  
    REP(i, w) cout << ans[i]+1 << "\n";  
    cout << flush;  
      
    return 0;  
}  

解法2

一段下る場合，偶数番目の列と奇数番目の列がswapされる．偶数番目の列と奇数番目の列に分割して管理しておくとswapするだけで1段下る操作を実行することができ で可能．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll h, w, n;  
    cin >> h >> w >> n;  
    vector<vector<ll>> v(h);  
    REP(i, n) {  
        ll a, b;  
        cin >> a >> b;  
        a--, b--;  
        v[a].push_back(b);  
    }  
  
    deque<ll> dq1, dq2;  
    for(ll i=0; i<w; i+=2) {  
        dq1.push_back(i);  
        dq2.push_back(i+1);  
    }  
    dump(dq1, dq2);  
    REP(i, h) {  
        if(i%2==0) {  
            swap(dq1, dq2);  
        } else {  
            ll f = dq1.front(), t = dq2.back();  
            dq1.pop_front();  
            dq2.pop_back();  
            swap(dq1, dq2);  
            dq1.push_front(f);  
            dq2.push_back(t);  
        }  
  
        for(auto j: v[i]) {  
            if(j%2==0) {  
                ll l = dq1[j/2], r = dq2[j/2];  
                dq1[j/2] = r;  
                dq2[j/2] = l;  
            } else {  
                ll l = dq1[(j+1)/2], r = dq2[j/2];  
                dq1[(j+1)/2] = r;  
                dq2[j/2] = l;  
            }  
        }  
        dump(dq1, dq2);  
    }  
  
    vector<ll> ans(w);  
    REP(i, w/2) {  
        ans[dq1[i]] = i*2;  
        ans[dq2[i]] = i*2+1;  
    }  
    for(auto i: ans) cout << i+1 << "\n";  
    cout << flush;  
  
    return 0;  
}  
``