AtCoder Regular Contest 041

Submission #605380

Source codeソースコード

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
using namespace std;

typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)


int main(int argc, char const *argv[]) {
  int N,L;
  cin >>N >>L;

  vector<int> x(N);
  vector<char> d(N);

  //i番目の区間で、(Rの出現数,Lの出現数)
  int ct[100000][2]={0};
  int ct_index=0;

  //今は左向きのうさぎを観測する区域か
  bool left=true;

  REP(i,N){
    scanf(" %d %c", &x[i], &d[i]);

    if(left){ //左向きのうさぎを観測すべき区域
      if(d[i]=='L'){
        ++ct[ct_index][1];
      }
      else{
        ++ct_index;
        ++ct[ct_index][0];
        left=false;
      }
    }
    else{
      if(d[i]=='R'){
        ++ct[ct_index][0];
      }
      else{
        ++ct[ct_index][1];
        left=true;
      }
    }
  }

  long ans=0;
  int now=-1; //見終わったindex
  REP(i, ct_index+1){
    //printf("kukan %d: R %d, L %d\n", i, ct[i][0], ct[i][1]);

    int base;
    //左向きのウサギの方が多いので、左に詰める
    if(ct[i][0]<=ct[i][1]){
      //indexを見る
      base=now+ct[i][0];
      //座標を入れる
      if(base==-1) base=0; //左端
      else base=x[base];

      int gap=1;
      //右に詰める
      for(int j=now+ct[i][0]-1; j>=now+1; --j){
        ans+=(base-gap)-x[j];
        ++gap;
      }

      gap=1;
      now=now+ct[i][0];
      //左に詰める
      for(int j=now+1; j<=now+ct[i][1]; ++j){
        ans+=x[j]-(base+gap);
        ++gap;
      }
      now=now+ct[i][1];
    }
    else{ //右に詰める
      //indexを見る
      base=now+ct[i][0]+1;
      //座標を入れる
      if(base==N) base=L+1; //右端
      else base=x[base];
      int gap=1;

      //右に詰める
      for(int j=now+ct[i][0]; j>=now+1; --j){
        ans+=(base-gap)-x[j];
        ++gap;
      }

      gap=1;
      now=now+ct[i][0]+1;
      //左に詰める
      for(int j=now+1; j<=now+ct[i][1]-1; ++j){
        ans+=x[j]-(base+gap);
        ++gap;
      }
      now=now+ct[i][1]-1;

    }

  }

  printf("%ld\n", ans);

  return 0;
}

Submission

Task問題 C - ウサギ跳び
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 AC
Score得点 100
Source lengthソースコード長 2579 Byte
File nameファイル名
Exec time実行時間 69 ms
Memory usageメモリ使用量 2388 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:40:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %c", &x[i], &d[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 100 / 100 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_26.txt,subtask1_27.txt,subtask1_28.txt,subtask1_29.txt,subtask1_30.txt,subtask1_31.txt,subtask1_32.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 39 ms 1980 KB
sample_02.txt AC 34 ms 1784 KB
sample_03.txt AC 33 ms 1912 KB
subtask1_01.txt AC 32 ms 1812 KB
subtask1_02.txt AC 31 ms 1792 KB
subtask1_03.txt AC 57 ms 2308 KB
subtask1_04.txt AC 57 ms 2388 KB
subtask1_05.txt AC 59 ms 2308 KB
subtask1_06.txt AC 60 ms 2300 KB
subtask1_07.txt AC 59 ms 2300 KB
subtask1_08.txt AC 62 ms 2308 KB
subtask1_09.txt AC 69 ms 2320 KB
subtask1_10.txt AC 60 ms 2324 KB
subtask1_11.txt AC 61 ms 2304 KB
subtask1_12.txt AC 58 ms 2372 KB
subtask1_13.txt AC 61 ms 2328 KB
subtask1_14.txt AC 62 ms 2360 KB
subtask1_15.txt AC 62 ms 2320 KB
subtask1_16.txt AC 63 ms 2320 KB
subtask1_17.txt AC 46 ms 2108 KB
subtask1_18.txt AC 48 ms 2040 KB
subtask1_19.txt AC 37 ms 1924 KB
subtask1_20.txt AC 57 ms 2328 KB
subtask1_21.txt AC 41 ms 1976 KB
subtask1_22.txt AC 44 ms 2108 KB
subtask1_23.txt AC 53 ms 2300 KB
subtask1_24.txt AC 41 ms 2044 KB
subtask1_25.txt AC 56 ms 2244 KB
subtask1_26.txt AC 61 ms 2304 KB
subtask1_27.txt AC 34 ms 1920 KB
subtask1_28.txt AC 61 ms 2296 KB
subtask1_29.txt AC 53 ms 2176 KB
subtask1_30.txt AC 40 ms 1920 KB
subtask1_31.txt AC 54 ms 2104 KB
subtask1_32.txt AC 63 ms 2304 KB