#826591 (C) No.5011 Better Mo's Algorithm is Needed!! (Weighted)

• 問題: No.5011 Better Mo's Algorithm is Needed!! (Weighted)
• ユーザー: chro_96
• 提出日時: 2022-12-17 23:15:38
• 言語: C (gcc 13.3.0)
• 結果: AC
• 実行時間: 110 ms / 5,000 ms
• コード長: 9,007 bytes
• コンパイル時間: 679 ms
• 実行使用メモリ: 8,208 KB
• スコア: 129,145,149
• 最終ジャッジ日時: 2022-12-17 23:20:12
• 合計ジャッジ時間: 43,560 ms
• ジャッジサーバーID （参考情報）: judge16 / judge11

ファイルパターン	結果
other	AC * 120

ソースコード

#include <stdio.h>
#include <stdlib.h>

int main () {
  int n = 0;
  int q = 0;
  int wt = 0;
  int st = 0;
  long long w[200000] = {};
  int l[200000] = {};
  int r[200000] = {};
  
  int res = 0;
  
  int ans[200000] = {};
  long long score = 0LL;
  
  int work[200000] = {};
  long long work_score = 0LL;
  
  long long sum_w[200001] = {};
  
  int t = 1000;
  
  res = scanf("%d", &n);
  res = scanf("%d", &q);
  res = scanf("%d", &wt);
  res = scanf("%d", &st);
  for (int i = 0; i < n; i++) {
    res = scanf("%lld", w+i);
    sum_w[i+1] = sum_w[i]+w[i];
  }
  for (int i = 0; i < q; i++) {
    res = scanf("%d", l+i);
    res = scanf("%d", r+i);
    l[i]--;
    r[i]--;
  }
  
  srand(1);
  
  score = sum_w[r[0]+1]-sum_w[l[0]];
  for (int i = 1; i < q; i++) {
    ans[i] = i;
    work[i] = i;
    if (l[i-1] < l[i]) {
      score += sum_w[l[i]]-sum_w[l[i-1]];
    } else {
      score += sum_w[l[i-1]]-sum_w[l[i]];
    }
    if (r[i-1] < r[i]) {
      score += sum_w[r[i]+1]-sum_w[r[i-1]+1];
    } else {
      score += sum_w[r[i-1]+1]-sum_w[r[i]+1];
    }
  }
  work_score = score;
  
  while (t > 0) {
    int idx1 = rand()%q;
    int idx2 = rand()%q;
    long long tmp_score = work_score;
    while (idx1 == idx2) {
      idx2 = rand()%q;
    }
    if (idx1 > idx2) {
      int swap = idx2;
      idx2 = idx1;
      idx1 = swap;
    }
    if (idx1+1 == idx2) {
      if (idx1 <= 0) {
        tmp_score -= sum_w[r[work[idx1]]+1]-sum_w[l[work[idx1]]];
        tmp_score += sum_w[r[work[idx2]]+1]-sum_w[l[work[idx2]]];
        if (l[work[idx1]] < l[work[idx2+1]]) {
          tmp_score += sum_w[l[work[idx2+1]]]-sum_w[l[work[idx1]]];
        } else {
          tmp_score += sum_w[l[work[idx1]]]-sum_w[l[work[idx2+1]]];
        }
        if (r[work[idx1]] < r[work[idx2+1]]) {
          tmp_score += sum_w[r[work[idx2+1]]+1]-sum_w[r[work[idx1]]+1];
        } else {
          tmp_score += sum_w[r[work[idx1]]+1]-sum_w[r[work[idx2+1]]+1];
        }
        if (l[work[idx2]] < l[work[idx2+1]]) {
          tmp_score -= sum_w[l[work[idx2+1]]]-sum_w[l[work[idx2]]];
        } else {
          tmp_score -= sum_w[l[work[idx2]]]-sum_w[l[work[idx2+1]]];
        }
        if (r[work[idx2]] < r[work[idx2+1]]) {
          tmp_score -= sum_w[r[work[idx2+1]]+1]-sum_w[r[work[idx2]]+1];
        } else {
          tmp_score -= sum_w[r[work[idx2]]+1]-sum_w[r[work[idx2+1]]+1];
        }
      } else if (idx2+1 == q) {
        if (l[work[idx1]] < l[work[idx1-1]]) {
          tmp_score -= sum_w[l[work[idx1-1]]]-sum_w[l[work[idx1]]];
        } else {
          tmp_score -= sum_w[l[work[idx1]]]-sum_w[l[work[idx1-1]]];
        }
        if (r[work[idx1]] < r[work[idx1-1]]) {
          tmp_score -= sum_w[r[work[idx1-1]]+1]-sum_w[r[work[idx1]]+1];
        } else {
          tmp_score -= sum_w[r[work[idx1]]+1]-sum_w[r[work[idx1-1]]+1];
        }
        if (l[work[idx2]] < l[work[idx1-1]]) {
          tmp_score += sum_w[l[work[idx1-1]]]-sum_w[l[work[idx2]]];
        } else {
          tmp_score += sum_w[l[work[idx2]]]-sum_w[l[work[idx1-1]]];
        }
        if (r[work[idx2]] < r[work[idx1-1]]) {
          tmp_score += sum_w[r[work[idx1-1]]+1]-sum_w[r[work[idx2]]+1];
        } else {
          tmp_score += sum_w[r[work[idx2]]+1]-sum_w[r[work[idx1-1]]+1];
        }
      } else {
        if (l[work[idx1]] < l[work[idx1-1]]) {
          tmp_score -= sum_w[l[work[idx1-1]]]-sum_w[l[work[idx1]]];
        } else {
          tmp_score -= sum_w[l[work[idx1]]]-sum_w[l[work[idx1-1]]];
        }
        if (r[work[idx1]] < r[work[idx1-1]]) {
          tmp_score -= sum_w[r[work[idx1-1]]+1]-sum_w[r[work[idx1]]+1];
        } else {
          tmp_score -= sum_w[r[work[idx1]]+1]-sum_w[r[work[idx1-1]]+1];
        }
        if (l[work[idx2]] < l[work[idx1-1]]) {
          tmp_score += sum_w[l[work[idx1-1]]]-sum_w[l[work[idx2]]];
        } else {
          tmp_score += sum_w[l[work[idx2]]]-sum_w[l[work[idx1-1]]];
        }
        if (r[work[idx2]] < r[work[idx1-1]]) {
          tmp_score += sum_w[r[work[idx1-1]]+1]-sum_w[r[work[idx2]]+1];
        } else {
          tmp_score += sum_w[r[work[idx2]]+1]-sum_w[r[work[idx1-1]]+1];
        }
        if (l[work[idx1]] < l[work[idx2+1]]) {
          tmp_score += sum_w[l[work[idx2+1]]]-sum_w[l[work[idx1]]];
        } else {
          tmp_score += sum_w[l[work[idx1]]]-sum_w[l[work[idx2+1]]];
        }
        if (r[work[idx1]] < r[work[idx2+1]]) {
          tmp_score += sum_w[r[work[idx2+1]]+1]-sum_w[r[work[idx1]]+1];
        } else {
          tmp_score += sum_w[r[work[idx1]]+1]-sum_w[r[work[idx2+1]]+1];
        }
        if (l[work[idx2]] < l[work[idx2+1]]) {
          tmp_score -= sum_w[l[work[idx2+1]]]-sum_w[l[work[idx2]]];
        } else {
          tmp_score -= sum_w[l[work[idx2]]]-sum_w[l[work[idx2+1]]];
        }
        if (r[work[idx2]] < r[work[idx2+1]]) {
          tmp_score -= sum_w[r[work[idx2+1]]+1]-sum_w[r[work[idx2]]+1];
        } else {
          tmp_score -= sum_w[r[work[idx2]]+1]-sum_w[r[work[idx2+1]]+1];
        }
      }
    } else {
      if (idx1 <= 0) {
        tmp_score -= sum_w[r[work[idx1]]+1]-sum_w[l[work[idx1]]];
        tmp_score += sum_w[r[work[idx2]]+1]-sum_w[l[work[idx2]]];
      } else {
        if (l[work[idx1]] < l[work[idx1-1]]) {
          tmp_score -= sum_w[l[work[idx1-1]]]-sum_w[l[work[idx1]]];
        } else {
          tmp_score -= sum_w[l[work[idx1]]]-sum_w[l[work[idx1-1]]];
        }
        if (r[work[idx1]] < r[work[idx1-1]]) {
          tmp_score -= sum_w[r[work[idx1-1]]+1]-sum_w[r[work[idx1]]+1];
        } else {
          tmp_score -= sum_w[r[work[idx1]]+1]-sum_w[r[work[idx1-1]]+1];
        }
        if (l[work[idx2]] < l[work[idx1-1]]) {
          tmp_score += sum_w[l[work[idx1-1]]]-sum_w[l[work[idx2]]];
        } else {
          tmp_score += sum_w[l[work[idx2]]]-sum_w[l[work[idx1-1]]];
        }
        if (r[work[idx2]] < r[work[idx1-1]]) {
          tmp_score += sum_w[r[work[idx1-1]]+1]-sum_w[r[work[idx2]]+1];
        } else {
          tmp_score += sum_w[r[work[idx2]]+1]-sum_w[r[work[idx1-1]]+1];
        }
      }
      if (idx2+1 != q) {
        if (l[work[idx1]] < l[work[idx2+1]]) {
          tmp_score += sum_w[l[work[idx2+1]]]-sum_w[l[work[idx1]]];
        } else {
          tmp_score += sum_w[l[work[idx1]]]-sum_w[l[work[idx2+1]]];
        }
        if (r[work[idx1]] < r[work[idx2+1]]) {
          tmp_score += sum_w[r[work[idx2+1]]+1]-sum_w[r[work[idx1]]+1];
        } else {
          tmp_score += sum_w[r[work[idx1]]+1]-sum_w[r[work[idx2+1]]+1];
        }
        if (l[work[idx2]] < l[work[idx2+1]]) {
          tmp_score -= sum_w[l[work[idx2+1]]]-sum_w[l[work[idx2]]];
        } else {
          tmp_score -= sum_w[l[work[idx2]]]-sum_w[l[work[idx2+1]]];
        }
        if (r[work[idx2]] < r[work[idx2+1]]) {
          tmp_score -= sum_w[r[work[idx2+1]]+1]-sum_w[r[work[idx2]]+1];
        } else {
          tmp_score -= sum_w[r[work[idx2]]+1]-sum_w[r[work[idx2+1]]+1];
        }
      }
      if (l[work[idx1]] < l[work[idx1+1]]) {
        tmp_score -= sum_w[l[work[idx1+1]]]-sum_w[l[work[idx1]]];
      } else {
        tmp_score -= sum_w[l[work[idx1]]]-sum_w[l[work[idx1+1]]];
      }
      if (r[work[idx1]] < r[work[idx1+1]]) {
        tmp_score -= sum_w[r[work[idx1+1]]+1]-sum_w[r[work[idx1]]+1];
      } else {
        tmp_score -= sum_w[r[work[idx1]]+1]-sum_w[r[work[idx1+1]]+1];
      }
      if (l[work[idx2]] < l[work[idx1+1]]) {
        tmp_score += sum_w[l[work[idx1+1]]]-sum_w[l[work[idx2]]];
      } else {
        tmp_score += sum_w[l[work[idx2]]]-sum_w[l[work[idx1+1]]];
      }
      if (r[work[idx2]] < r[work[idx1+1]]) {
        tmp_score += sum_w[r[work[idx1+1]]+1]-sum_w[r[work[idx2]]+1];
      } else {
        tmp_score += sum_w[r[work[idx2]]+1]-sum_w[r[work[idx1+1]]+1];
      }
      if (l[work[idx1]] < l[work[idx2-1]]) {
        tmp_score += sum_w[l[work[idx2-1]]]-sum_w[l[work[idx1]]];
      } else {
        tmp_score += sum_w[l[work[idx1]]]-sum_w[l[work[idx2-1]]];
      }
      if (r[work[idx1]] < r[work[idx2-1]]) {
        tmp_score += sum_w[r[work[idx2-1]]+1]-sum_w[r[work[idx1]]+1];
      } else {
        tmp_score += sum_w[r[work[idx1]]+1]-sum_w[r[work[idx2-1]]+1];
      }
      if (l[work[idx2]] < l[work[idx2-1]]) {
        tmp_score -= sum_w[l[work[idx2-1]]]-sum_w[l[work[idx2]]];
      } else {
        tmp_score -= sum_w[l[work[idx2]]]-sum_w[l[work[idx2-1]]];
      }
      if (r[work[idx2]] < r[work[idx2-1]]) {
        tmp_score -= sum_w[r[work[idx2-1]]+1]-sum_w[r[work[idx2]]+1];
      } else {
        tmp_score -= sum_w[r[work[idx2]]+1]-sum_w[r[work[idx2-1]]+1];
      }
    }
    if (tmp_score < work_score) {
      int swap = work[idx1];
      work[idx1] = work[idx2];
      work[idx2] = swap;
      work_score = tmp_score;
    }
    if (work_score < score) {
      score = work_score;
      for (int i = 0; i < q; i++) {
        ans[i] = work[i];
      }
    }
    t--;
  }
  
  printf("%d", ans[0]+1);
  for (int i = 1; i < q; i++) {
    printf(" %d", ans[i]+1);
  }
  printf("\n");
  
  return 0;
}