Submission #3598838


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("O3","unroll-loops")
#pragma GCC target ("avx")

#define hi cout<<"hi"<<endl

//シンプルにシミュレートするやつは学校のやつで27500

int inputmap[100][100],ansmap[100][100];
const int Q = 1000;
const int dx[4]={1,1,-1,-1},dy[4]={-1,1,1,-1};
const int dxy[7]={1,1,-1,-1,1,1,-1};
int LoopCount,ChangeCount;
int state[1000][3];
int Ansstate[1000][3];
int AnsScore;
int MaxScore;
clock_t StartClock;


inline int mymax(int a,int b){
    return a<b&&(a=b),a;
}

inline int mymin(int a,int b){
    return a>b&&(a=b),a;
}

inline int myabs(int a){
    return (a^(a>>31))-(a>>31);
}

uint32_t XorShift(void) {
	static uint32_t x = 123456789;
	static uint32_t y = 362436069;
	static uint32_t z = 521288629;
	static uint32_t w = 88675123;
	uint32_t t;

	t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

double Prob(void){
	double ret=(double)XorShift()/UINT_MAX;
	return ret;
}

void output(){
	cout<<Q<<endl;
	for(int i=0;i<Q;i++){
		cout<<Ansstate[i][1]<<' '<<Ansstate[i][0]<<' '<<Ansstate[i][2]<<endl;
	}

}

void ResultDump(){
	cerr<<LoopCount<<','<<ChangeCount<<','<<(double)ChangeCount/LoopCount<<endl;
	cerr<<AnsScore<<endl;
}

void input(){
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			cin>>inputmap[i][j];
		}
	}
}

bool CanOperate(int y,int x){
	return x>=0&&y>=0&&x<100&&y<100;
}

int JudgeScore(){
	int ret=200000000;
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			ret-=myabs((inputmap[i][j]-ansmap[i][j]));
		}
	}
	return ret;
}

double MetropolisHastings(int dif,double t){
    double ret=exp(dif/t);
    return ret;
}

void SimpleAddYamagata(int y,int x,int h){
    /*for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            ansmap[i][j]+=max(0,h-abs(i-y)-abs(j-x));
        }
    }*/
	for(int i=mymax(0,y-h+1);i<mymin(100,y+h-1);i++){
		for(int j=mymax(0,x-h+1);j<mymin(100,x+h-1);j++){
			ansmap[i][j]+=mymax(0,h-myabs(y-i)-myabs(x-j));
		}
	}
}

void SimpleSubYamagata(int y,int x,int h){
    /*for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            ansmap[i][j]-=max(0,h-abs(i-y)-abs(j-x));
        }
    }*/
	for(int i=mymax(0,y-h+1);i<mymin(100,y+h-1);i++){
		for(int j=mymax(0,x-h+1);j<mymin(100,x+h-1);j++){
			ansmap[i][j]-=mymax(0,h-myabs(y-i)-myabs(x-j));
		}
	}
}

void addx(int y,int x,int h){
    
    REP(i,max(x-h-1,0),x+1)REP(j,max(y+abs(x-i)-h,0),min(y-abs(x-i)+h+1,n)){
        ++a[i][j];
    }
    REP(i,x+1,min(x+h+2,n))REP(j,max(y+abs(x+1-i)-h,0),min(y-abs(x+1-i)+h+1,n)){
        --a[i][j];
    }
    for(int i=mymax(x-h-1,0);i<x+1;i++){
        for(int j=mymax(y+myabs(x-i)-h,0);j<mymin(y-abs(x-i)+h+1,100);j++){
            ansmap[i][j]++;
        }
    }
    for(int )
}

void subx(int y,int x,int h){
    for(int i=mymax(0,y-h+1);i<(100,y+h-1);i++){
        for(int j=mymax(0,x-h);j<mymin(100,x);j++){
            ++ansmap[i][j];
        }
        for(int j=mymin(100,x);j<(100,x+h-1);j++){
            --ansmap[i][j];
        }
    }
}

void addy(int y,int x,int h){
    
}

void init(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	input();
	StartClock=clock();
	for(int i=0;i<Q;i++){
		int y,x,h;
		y=XorShift()%100;
		x=XorShift()%100;
		h=XorShift()%100+1;
		//cout<<y<<','<<x<<','<<h<<endl;
		SimpleAddYamagata(y,x,h);
		state[i][0]=y;
		state[i][1]=x;
		state[i][2]=h;
		Ansstate[i][0]=y;
		Ansstate[i][1]=x;
		Ansstate[i][2]=h;
	}
	MaxScore=JudgeScore();
	AnsScore=MaxScore;
}

void SimpleRandomGreedyAndSimulatedAnnealing(){
	/*while(MaxScore<199600000){
		LoopCount++;
		int rnd=XorShift()%1000;
		//cout<<rnd<<endl;
		int ny=state[rnd][0];
		int nx=state[rnd][1];
		int nh=state[rnd][2];
		int ty=XorShift()%100;
		int tx=XorShift()%100;
		int th=XorShift()%100+1;
		SimpleSubYamagata(ny,nx,nh);
		SimpleAddYamagata(ty,tx,th);
		int TmpScore=JudgeScore();
		if(MaxScore<TmpScore){
			state[rnd][0]=ty;
			state[rnd][1]=tx;
			state[rnd][2]=th;
			MaxScore=TmpScore;
			ChangeCount++;
			AnsScore=TmpScore;
			Ansstate[rnd][0]=ty;
			Ansstate[rnd][1]=tx;
			Ansstate[rnd][2]=th;
			//cout<<LoopCount<<','<<ChangeCount<<','<<MaxScore<<endl;
			//cerr<<LoopCount<<endl;
		}else{
			SimpleSubYamagata(ty,tx,th);
			SimpleAddYamagata(ny,nx,nh);
		}
		//cout<<total_time.get_time()<<endl;
	}*/
	double T0=170.0;//75+-1未満(B=4.0,A=1.0(B=1.0も))(100で1.0,1.0で67)//210tamesitoite
	int n=165000;//動かないも遷移では
	double itr=0.5;
	double paramA=1.0;
	double paramB=1.0;
	double cpyT;
	int RndCount=0;
	while(clock()-StartClock<= 5.99*CLOCKS_PER_SEC){
	//for(int lct=0;lct<140000;lct++){
		itr+=1.0;
		double progress=itr/n;
		double remain=(1.0-progress);
		double T=T0*pow(remain,paramA)*exp2(-progress*paramB);
		LoopCount++;
		int prnd=XorShift()%1000;//placernd
		//cout<<rnd<<endl;
		int ny=state[prnd][0];
		int nx=state[prnd][1];
		int nh=state[prnd][2];
		int vrnd=XorShift()%3;//varrnd
		int trnd=XorShift()%2;
		int ty=ny;
		int tx=nx;
		int th=nh;

		if(trnd==0)trnd=-1;//独立に動かす(あんま効果ない)(比較回数が足りない)(68付近で頭打ち)速度がほしい()速度さえあれば理論上99991くらいまで行ける
		if(vrnd==0){
			ty+=trnd;
		}else if(vrnd==1){
			tx+=trnd;
		}else if(vrnd==2){
			th+=trnd;
		}

		/*ty+=((XorShift()%3)-1);//従属に動かす(68付近まで詰めれる)
		tx+=((XorShift()%3)-1);
		th+=((XorShift()%3)-1);*/

		if((!(CanOperate(ty,tx)&&th>0&&th<=100)))continue;//比較が比較的重そうなので消した(ダジャレ)
		SimpleSubYamagata(ny,nx,nh);
		SimpleAddYamagata(ty,tx,th);
		int TmpScore=JudgeScore();

		//diffscore=TmpScore-MaxScore
		if(MaxScore<TmpScore){
			state[prnd][0]=ty;
			state[prnd][1]=tx;
			state[prnd][2]=th;
			MaxScore=TmpScore;
			if(MaxScore>AnsScore){
				AnsScore=MaxScore;
				for(int i=0;i<Q;i++){
					Ansstate[i][0]=state[i][0];
					Ansstate[i][1]=state[i][1];
					Ansstate[i][2]=state[i][2];
				}
			}
			ChangeCount++;
            //cout<<LoopCount<<','<<ChangeCount<<','<<MaxScore<<','<<T<<endl;
			//cerr<<LoopCount<<endl;
			//cout<<Prob()<<endl;
		}else if(MetropolisHastings(TmpScore-MaxScore,T)>Prob()){
		    //cout<<MetropolisHastings(TmpScore-MaxScore,T)<<endl;
		    RndCount++;
			state[prnd][0]=ty;
			state[prnd][1]=tx;
			state[prnd][2]=th;
			MaxScore=TmpScore;
			ChangeCount++;
			//cout<<LoopCount<<','<<ChangeCount<<','<<MaxScore<<','<<T<<endl;
		}
		else{
			SimpleSubYamagata(ty,tx,th);
			SimpleAddYamagata(ny,nx,nh);
		}
		//cout<<total_time.get_time()<<endl;
		//cpyT=T;
	}
	//cout<<cpyT<<endl;
}

main(){
	init();

	//cout<<0<<','<<0<<','<<MaxScore<<endl;
	//SimpleRandomGreedy();
	//HillClimb();
	//SimpleRandomGreedyAndHillClimb();
	//SimulatedAnnealing();
	SimpleRandomGreedyAndSimulatedAnnealing();
	//SimpleSimpleRandomGreedyAndSimulatedAnnealing();
	//SimulatedCrystallization();
	output();
	//cout<<clock()-StartClock<<endl;
	ResultDump();
}

Submission Info

Submission Time
Task A - 積雪深差
User masu1208
Language C++14 (GCC 5.4.1)
Score 0
Code Size 7245 Byte
Status CE

Compile Error

./Main.cpp: In function ‘void addx(int, int, int)’:
./Main.cpp:121:9: error: ‘i’ was not declared in this scope
     REP(i,max(x-h-1,0),x+1)REP(j,max(y+abs(x-i)-h,0),min(y-abs(x-i)+h+1,n)){
         ^
./Main.cpp:121:27: error: ‘REP’ was not declared in this scope
     REP(i,max(x-h-1,0),x+1)REP(j,max(y+abs(x-i)-h,0),min(y-abs(x-i)+h+1,n)){
                           ^
./Main.cpp:124:25: error: ‘n’ was not declared in this scope
     REP(i,x+1,min(x+h+2,n))REP(j,max(y+abs(x+1-i)-h,0),min(y-abs(x+1-i)+h+1,n)){
                         ^
./Main.cpp:132:13: error: expected unqualified-id before ‘)’ token
     for(int )
             ^
./Main.cpp:132:13: error: expected ‘;’ before ‘)’ token
./Main.cpp:132:13: error: expected primary-expression before ‘)’ token
./Main.cpp:132:13: error: expected ‘;’ before ‘)’ token
./Main.cpp:133:1: error: expected primary-expression before ‘}’ token
 }
 ^