結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
ユーザー lanegue
提出日時 2023-12-15 08:34:54
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 66 ms / 3,000 ms
コード長 1,709 bytes
コンパイル時間 2,020 ms
コンパイル使用メモリ 109,760 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-27 06:03:40
合計ジャッジ時間 3,935 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.array;
import std.range;
import core.bitop;

const ulong N = 28;

ulong[][] combinations(ulong m, ulong[] g, ulong[] h){
  ulong[][] result = new ulong[][N / 2 + 1];
  for(ulong i = 0; i < 2 ^^ (N / 2); i++){
    ulong s = 0;
    for(auto j = 0; j < N / 2; j++){
      if((i >> j) & 1){
        s += g[j];
      }else{
        s += h[j];
      }
    }
    result[i.popcnt] ~= s % m;
  }
  for(auto i = 0; i < N / 2; i++){
    result[i].sort;
  }
  return result;
}

ulong solve(ulong m, ulong k, ulong x, ulong[][] h1, ulong[][] h2){
  ulong result = 0;
  for(auto i = (k < N / 2) ? 0 : (k - N / 2); i <= k && i <= N / 2; i++){
    long min = h1[i].length - 1;
    long max = h1[i].length - 1;
    for(auto j = 0; j < h2[k - i].length; j++){
      while(min >= 0 && h1[i][min] + h2[k - i][j] >= x){
        min--;
      }
      while(max > min && (h1[i][max] + h2[k - i][j]) >= m){
        max--;
      }
      result += max - min;
    }
    min = 0;
    max = h1[i].length;
    for(long j = h2[k - i].length - 1; j >= 0; j--){
      while(min < max && h1[i][min] + h2[k - i][j] < m + x){
        min++;
      }
      result += max - min;
    }
  }
  return result;
}

void main(){
  auto M = readln.chomp.to!ulong;
  auto G = readln.chomp.split.to!(ulong[]);
  auto H = readln.chomp.split.to!(ulong[]);
  auto h1 = combinations(M, G[0 .. N / 2], H[0 .. N / 2]);
  auto h2 = combinations(M, G[N / 2 .. N], H[N / 2 .. N]);
  auto Q = readln.chomp.to!int;
  for(auto q = 0; q < Q; q++){
    auto input = readln.chomp.split.to!(long[]);
    auto k = input[0];
    auto x = input[1];
    solve(M, k, x, h1, h2).writeln;
  }
}
0