Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #71 B問題 - Colorful Field (この記事を編集する[管理者用])

Source

Codeforces Beta Round #71 B問題 (1000pt)
Problem description
Beta Round #71の自分の参加記録

問題概要

n*m (40000*40000以下) のグリッドを考える.
k個 (10^3以下) だけ使えないマスが与えられる.
使えないグリッドを飛ばしながら,row-major orderで
 人参,キウィ,ぶどう,人参,キウィ,ぶどう,人参,キウィ,ぶどう,…
と置いていく.
t個 (10^3以下) のマスが与えられるので,それぞれ,そのマスに何があるか,もしくは使えないマスか,を答える問題.

解法

自分より前の置いたマスの数を数えて,それのmod 3で答えがわかる.
自分より前のマスの数はすぐ計算できるので,自分より前の使えないマスの数を数えれば良いことになる.
使えないマスの数は高々10^3しかないので,全部調べればいい.クエリが10^3個あるのを加味しても全体で高々10^6程度の計算でいける.
使えないマスの数を二分探索すれば速くなる.
以下のコードはあんまりよろしくないコード.
行ごとに使えないマスの数を覚えておいて,該当する行だけ全部調べるという無駄にややこしくして計算量は落ちてないという….

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)

typedef struct struct_vector_int{ int size,mem; int *d; }intVector;
intVector intVectorNull(){ intVector v; v.size=v.mem=0; return v; }

void intVectorMemoryExpand(intVector *v){
  int i, *t, m;
  m=v->mem*2; if(m<5) m=5;
  t=(int*)malloc(m*sizeof(int));
  rep(i,v->size) t[i]=v->d[i];
  if(v->mem) free(v->d);
  v->d=t; v->mem=m;
}

void intVectorPushBack(intVector *v,int add){
  if(v->mem==v->size) intVectorMemoryExpand(v);
  v->d[(v->size)++] = add;
}

void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}

intVector waste[50001];
int sum[50001];

int main(){
  int i,j,k,l,m,n,t,q;
  int x,y;
  int a,b,res;
  char *out[]={"Carrots","Kiwis","Grapes","Waste"};

  rep(i,50001) waste[i] = intVectorNull();

  while(scanf("%d%d%d%d",&x,&y,&t,&q)==4){
    rep(i,x) waste[i].size = 0;
    while(t--){
      scanf("%d%d",&i,&j); i--; j--;
      intVectorPushBack(waste+i,j);
    }
    rep(i,x) intSort(waste[i].d, waste[i].size);

    sum[0]=0;
    rep(i,x) sum[i+1] = sum[i]+waste[i].size;

    while(q--){
      scanf("%d%d",&a,&b); a--; b--;
      res = (y*a-sum[a])%3;
      res = (res+b)%3;
      rep(i,waste[a].size){
        k = waste[a].d[i];
        if(k==b){ res=3; break; }
        if(k>b) break;
        res = (res+2)%3;
      }
      puts(out[res]);
    }
  }


  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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