Codeforces Global Round 3 C問題 - Crazy Diamond

Source

Codeforces Global Round 3 C問題 (1500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20190601-1)のコード

C++に変換後のコードはこちら

//no-unlocked
int N, P[3d5];
int inv[3d5];

int M, A[15d5], B[15d5];

void swap_sub(int a, int b){
  swap(P[a], P[b]);
  swap(inv[P[a]], inv[P[b]]);
  A[M] = a+1;
  B[M++] = b+1;
}

void swap_main(int a, int b){
  if(a > b) swap(a,b);

  if(b-a >= N/2){
    swap_sub(a,b);
    return;
  }

  if( a >= N/2 && b >= N/2 ){
    swap_sub(0,a);
    swap_sub(0,b);
    swap_sub(0,a);
    return;
  }

  if( N-1-a >= N/2 && N-1-b >= N/2 ){
    swap_sub(N-1,a);
    swap_sub(N-1,b);
    swap_sub(N-1,a);
    return;
  }

  swap_sub(0, b);
  swap_sub(a, N-1);
  swap_sub(0, N-1);
  swap_sub(0, b);
  swap_sub(a, N-1);
}

{
  int i, j, k;
  
  rd(N,P(N));
  rep(i,N) P[i]--;
  rep(i,N) inv[P[i]] = i;

  rep(i,N) if(P[i]!=i){
    swap_main(i, inv[i]);
  }

  wt(M);
  rep(i,M) wt(A[i],B[i]);
}

Current time: 2021年09月27日23時22分18秒
Last modified: 2019年06月02日04時30分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_3
トップページに戻る

Logged in as: unknown user (not login)

ログイン: