Codeforces Round #692 (based on Technocup 2021 Elimination Round 3) DIV1 D問題/DIV2 F問題/Round3 F問題 - The Thorny Path

Source

Codeforces Round #692 (based on Technocup 2021 Elimination Round 3) DIV1 D問題 (1750pt)
Codeforces Round #692 (based on Technocup 2021 Elimination Round 3) DIV2 F問題 (2750pt)
Technocup 2021 - Elimination Round 3 F問題 (2750pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201229-1）のコード

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

//no-unlocked
int N, P[1d6];
int sz, arr[1d6], cnt[5], tar[5];

{
  Permutation p;
  REP(rd_int()){
    Modint res = 1;
    int mn = 0, fg = 0;
    rd(N,(P--)(N));
    p.changeSize(N);
    rep(i,N) p[i] = P[i];
    sz = p.cycle_len(arr);

    rep(i,sz){
      while(arr[i] >= 5){
        arr[i] -= 3;
        res *= 3;
        N -= 3;
        mn++;
      }
    }
    rep(i,5) cnt[i] = 0;

    rep(i,sz) if(arr[i]) cnt[arr[i]]++;
    if(N % 3 == 1 && cnt[4]){
      cnt[4]--;
      res *= 4;
      N -= 4;
      fg = 1;
    }
    if(N % 3 == 1 && cnt[2] >= 2){
      cnt[2] -= 2;
      res *= 4;
      N -= 4;
    }
    if(N % 3 == 1 && cnt[1] >= 2 && cnt[2]){
      cnt[1] -= 2;
      cnt[2]--;
      res *= 4;
      N -= 4;
      mn += 1;
    }
    if(N % 3 == 1 && cnt[1] >= 4){
      cnt[1] -= 4;
      res *= 4;
      N -= 4;
      mn += 2;
      fg = 1;
    }
    if(N % 3 == 1 && cnt[1] && cnt[3]){
      cnt[1]--;
      cnt[3]--;
      res *= 4;
      N -= 4;
      mn++;
    }
    if(N % 3 == 2 && cnt[2]){
      cnt[2]--;
      res *= 2;
      N -= 2;
    }
    if(N % 3 == 2 && cnt[1] >= 2){
      cnt[1] -= 2;
      res *= 2;
      N -= 2;
      mn++;
    }
    if(N % 3 == 2 && cnt[4]){
      cnt[4]--;
      cnt[2]++;
      res *= 2;
      N -= 2;
      mn++;
    }
    while(cnt[4]){
      cnt[4]--;
      cnt[1]++;
      res *= 3;
      N -= 3;
      mn++;
    }
    while(cnt[1] && cnt[2]){
      cnt[1]--;
      cnt[2]--;
      res *= 3;
      N -= 3;
      mn++;
    }
    if(fg && cnt[2] >= 2) cnt[1]++, cnt[3]++, cnt[2]-=2, mn++;
    while(cnt[1] && cnt[2]){
      cnt[1]--;
      cnt[2]--;
      res *= 3;
      N -= 3;
      mn++;
    }
    while(cnt[1] >= 3){
      cnt[1] -= 3;
      res *= 3;
      N -= 3;
      mn += 2;
    }
    while(cnt[2] >= 3){
      cnt[2] -= 3;
      res *= 3;
      N -= 3;
      res *= 3;
      N -= 3;
      mn += 3;
    }
    while(cnt[3]){
      cnt[3]--;
      res *= 3;
      N -= 3;
    }

    wt(res,mn);
  }
}

Current time: 2024年04月19日20時11分51秒
Last modified: 2020年12月30日09時50分46秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF692 CF_DIV1_D CF_DIV2_F
トップページに戻る

Logged in as: unknown user (not login)