トロントに行きたいけどGCJは無理そうだからDCJの対策をする狼。二日目。

baby_blocks

ヤバすぎるTime Limit設定に全アフリカが泣いた。(実は3000万回クエリ読んでも1.8秒しかかからないという罠)
偏りすぎるのがやばいけどどうすんの、ってT個のブロックに等分した後左右から別のブロックに移動するタイミング約2N個をイベントソートして先頭N個だけ使えばいいんですね。
全く難しいアイデアではないし、異様にきつい制限時間だけが厄介。本番でこれ落とした人可哀想www何この11位の人画面の隅に変なキャラクター出しながらコーディングしてるんだけどうけるwwwww

メモ: 司令塔作るときは0番ノードよりT-1番ノードにした方がやりやすい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<message.h>
#include"baby_blocks.h"
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-10;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB
Send, Receive / 5 ~ 10ms?
Linear Message passing: slow (500ms through every nodes)

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
long long b_sum[110];
long long a_sum[110];
long long l_sum[110];
long long r_sum[110];
int val[10100000];
pair<long long,int> ev[210];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumberOfBlocks();
	int bk=T;
	if(N<T){
		T=N+1;
		if(I>=T)return 0;
	}
	
	if(I==T-1){
		for(int i=0;i<T-1;i++){
			Receive(i);
			b_sum[i]=GetLL(i);
		}
		for(int i=0;i<T-1;i++){
			l_sum[i]=r_sum[i]=b_sum[i];
		}
		for(int i=0;i<T-1;i++){
			l_sum[i+1]+=l_sum[i];
		}
		for(int i=T-2;i>=0;i--){
			r_sum[i]+=r_sum[i+1];
		}
		for(int i=0;i<T-1;i++){
			ev[i*2]=(make_pair(l_sum[i],0));
			ev[i*2+1]=(make_pair(r_sum[i],1));
		}
		std::sort(ev,ev+T*2-2);
		long long Loff=0;
		long long Roff=0;
		int l_bl=0;
		int r_bl=T-2;
	//	for(int i=0;i<T;i++){
	//		printf("%lld %d\n",ev[i].first,ev[i].second);fflush(stdout);
	//	}
		for(int i=0;i<T-1;i++){

			PutLL(i,Loff);
			PutLL(i,Roff);
			PutInt(i,l_bl);
			PutInt(i,r_bl);
			Send(i);

			if(ev[i].second==0){
				Loff=ev[i].first;
				l_bl++;
			}else{
				Roff=ev[i].first;
				r_bl--;
			}
		}
		int ret=0;
		for(int i=0;i<T-1;i++){
			Receive(i);
			ret+=GetInt(i);
		}
		printf("%d\n",ret-1);
	}else{
		long long L=(long long)N*I/(T-1);
		long long R=(long long)N*(I+1)/(T-1);
		for(int i=L;i<R;i++){
			int q=GetBlockWeight(i);
			b_sum[I]+=q;
		}
		PutLL(T-1,b_sum[I]);
		Send(T-1);
		Receive(T-1);
		long long Loff=GetLL(T-1);
		long long Roff=GetLL(T-1);
		int l_bl=GetInt(T-1);
		int r_bl=GetInt(T-1);
		long long at_L=(long long)N*l_bl/(T-1);
		long long at_R=(long long)N*(r_bl+1)/(T-1)-1;
		long long n_L=(long long)N*(l_bl+1)/(T-1);
		long long n_R=(long long)N*(r_bl)/(T-1)-1;
		int ret=0;
		while(1){
			if(at_L==n_L||at_R==n_R||at_L>at_R+1)break;
		//	printf("%lld %lld %lld %lld\n",at_L,at_R,n_L,n_R);
			if(Loff==Roff){
				ret++;
				Loff+=GetBlockWeight(at_L);
				at_L++;
				Roff+=GetBlockWeight(at_R);
				at_R--;
			}else if(Loff<Roff){
				Loff+=GetBlockWeight(at_L);
				at_L++;
			}else{
				Roff+=GetBlockWeight(at_R);
				at_R--;
			}
		}
		PutInt(T-1,ret);
		Send(T-1);
	}

}