tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM 498 Div1

試験一週間前に無理やり参加。

250:Foxなんたら
グラフの形がきつねの耳かどうかを判定する。
こういう問題はデバッグすると新たにバグを生んで落ちるだけ。
本当に配列やるだけの正確さが足りない。

450:Foxなんたら
適当に構造体つくってソートしてlower_boundとupper_bound使うだけ。
「これMediumなの?」ってレベルだけどこれなかったら0点だったのでまあありがたい。
(ちなみに初めてTopCoderリアルタイムでC++使った気がします)

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
	int size;
	struct D{
		int t[50];
	};
	bool operator<(const D& a,const D& b){
		for(int i=0;i<size;i++)
			if(a.t[i]<b.t[i])return true;
			else if(a.t[i]>b.t[i])return false;
		return false;
	}

class FoxStones{
	public:


		D dat[40000];
		bool visited[40000];
		bool table[200][200];
		int abs(int a){
			return a<0?-a:a;
		}
		long long fact(int a){
			long long ret=1;
			for(int i=0;i<a;i++)
				ret=ret*(i+1)%1000000009;
			return ret;
		}
		int getCount(int a,int b,vector<int> c,vector<int> d){
			long long ret=1;
			int now=0;
			size=c.size();
			for(int i=0;i<size;i++)table[c[i]-1][d[i]-1]=true;
			for(int i=0;i<a;i++)
				for(int j=0;j<b;j++){
					if(!table[i][j]){
						for(int k=0;k<size;k++)
							dat[now].t[k]=max(abs(c[k]-1-i),abs(d[k]-j-1));
						now++;
					}
				}
			
			std::sort(dat,dat+now);
			for(int i=0;i<now;i++){
				//for(int j=0;j<size;j++)printf("%d ",dat[i].t[j]);
				//printf("\n");
				if(!visited[i]){
					int begin=lower_bound(dat,dat+now,dat[i])-dat;
					int end=upper_bound(dat,dat+now,dat[i])-dat;
					
					for(int j=begin;j<end;j++)visited[j]=true;
					ret=ret*fact(end-begin)%1000000009;
				}
			}
			return (int)ret;
		}
};

ながったらしい。点数低すぎ。sortくらい使い方知れよ。

1000:Foxなんとか
知るかよ

Intermission
writerはir5さんかな〜 って考える。

Challenge Phase
前回のせいでChallengeする気がなくなってる。
しかしChallenge中にEasy間違ってることに気づく。あーあ。

System Test
450だけ通った
0 + 200くらい + 0 + 0 = 200くらい(497th)

Rating : 1283 -> 1295 (-INF)