結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0