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 } ^