Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1992-1f8ac596
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #72 DIV1 B問題/DIV2 D問題 - Doctor (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 B問題 (1000pt)
Codeforces Beta Round #72 DIV2 D問題 (2000pt)
Problem description
Beta Round #72 DIV1の自分の参加記録

問題概要

最初1~Nまで番号つけられたN人が順番に一列に並んでいる.(Nは10^5以下)
一番最初にいる人が,一番後ろに回るという操作をK (10^14以下) 回繰り返す.
ただし,番号kの人が,一番先頭にa[k] (10^9以下) 回目に来たときは,並び直さずに帰ってしまう.
最終的の列の状態を出力する問題.
K回も操作を行えないときはそれを指摘する.

解法

まず,何周完全にまわるか,というのを2分探索で求める.
残りの部分は普通にシミュレートするなり,なんとでもして求める.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int main(){
  int i,j,k,l,m,n,rest;
  ll sum, all;
  int in[120000], num[120000];
  ll a, b, c, tmp;

  while(scanf("%d%I64d",&n,&all)==2){
    rep(i,n) scanf("%d",in+i);
    sum = 0; rep(i,n) sum += in[i];

    if(sum < all){ puts("-1"); continue; }

    a = 0; b = 10000000000LL;
    while(a<b){
      c = (a+b+1)/2;
      tmp = 0;
      rep(i,n){
        if(c < in[i]) tmp += c;
        else          tmp += in[i];
      }

      if(tmp > all) b = c-1; else a = c;
    }

    rep(i,n){
      tmp = in[i];
      if(in[i] > a) tmp = a;
      all -= tmp; in[i] -= tmp;
    }

    rest = 0;
    rep(i,n) if(in[i]) num[rest] = in[i], in[rest++] = i;

    rep(i,rest){
      if(all+i >= rest && num[(all+i)%rest]==1) continue;
      if(i) putchar(' ');
      printf("%d",in[(all+i)%rest]+1);
    }
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1992-1f8ac596
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。