Submission #169615
Source Code Expand
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <utility>
#include <string>
#include <fstream>
#include <ios>
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <streambuf>
#include <complex>
#include <numeric>
#include <valarray>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdlib>
#include <cstddef>
#include <cstdarg>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <cwchar>
#include <cwctype>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;
typedef unsigned long long ull;
#define ALL(c) (c).begin(), (c).end()
#define CLEAR(v) memset(v,0,sizeof(v))
#define MP(a,b) make_pair((a),(b))
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ABS(a) ((a)>0?(a):-(a))
template<class T> T MIN(const T& a, const T& b) { return a < b ? a : b; }
template<class T> T MAX(const T& a, const T& b) { return a > b ? a : b; }
template<class T> void MIN_UPDATE(T& a, const T& b) { if (a > b) a = b; }
template<class T> void MAX_UPDATE(T& a, const T& b) { if (a < b) a = b; }
const int DX[] = { 0, 0, 1, -1 };
const int DY[] = { 1, -1, 0, 0 };
vector<pair<int, int> > initialMachines;
int N;
ll compressedBase[64][64];
vector<int> space(const vector<int>& xs, int X) {
vector<int> ret;
ret.push_back(xs[0] - 1);
ret.push_back(1);
REP(i, xs.size() - 1) {
ret.push_back(xs[i + 1] - xs[i] - 1);
ret.push_back(1);
}
ret.push_back(X - xs.back());
return ret;
}
ll calculate(const vector<pair<int, int> >& machines, ll compressedBase[64][64], int W, int H) {
ll compressed[64][64];
bool memo[64][64];
memcpy(compressed, compressedBase, sizeof(compressed));
CLEAR(memo);
ll counter = 0;
for (const auto& machine : machines) {
counter += compressed[machine.first][machine.second];
memo[machine.first][machine.second] = true;
REP(dir, 4) {
int x = machine.first + DX[dir];
int y = machine.second + DY[dir];
while (0 <= x && x < N * 2 + 1 && 0 <= y && y < N * 2 + 1 && !memo[x][y]) {
counter += compressed[x][y];
memo[x][y] = true;
x += DX[dir];
y += DY[dir];
}
}
}
return counter;
}
#ifdef _MSC_VER
#include <Windows.h>
ll getTime() {
return GetTickCount();
}
#else
#include <sys/time.h>
ll getTime() {
struct timeval tv;
gettimeofday(&tv, NULL);
ll result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
//cerr << result << endl;
return result;
}
#endif
// http://www.jstatsoft.org/v08/i14/xorshift.pdf
unsigned int xor128() { // 周期は 2^128-1
static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
//TODO:状態を表す型/構造体を作成する
class STATE {
public:
//TODO:コンストラクタに必要な引数を追加する
explicit STATE();
void next();
void prev();
double energy();
public:
vector<pair<int, int> > machines;
int src, dst;
};
class SimulatedAnnealing {
public:
//TODO:コンストラクタに必要な引数を追加する
SimulatedAnnealing();
STATE run();
private:
static const int TIME_LIMIT;
double calculateProbability(double score, double scoreNeighbor, double temperature);
};
//TODO:コンストラクタに必要な引数を追加する
SimulatedAnnealing::SimulatedAnnealing() {
}
//TODO:計算時間をミリ秒単位で設定する
const int SimulatedAnnealing::TIME_LIMIT = 3900;
STATE SimulatedAnnealing::run() {
const ll timeStart = getTime();
const ll timeEnd = timeStart + TIME_LIMIT;
STATE state;
double energy = state.energy();
STATE result = state;
double minEnergy = energy;
int counter = 0;
ll timeCurrent;
while ((timeCurrent = getTime()) < timeEnd){
REP(loop, 100) {
state.next();
const double energyNeighbor = state.energy();
const double random = xor128() * 0.00000000023283064365386962890625;
const double probability = calculateProbability(energy, energyNeighbor, (double)(timeEnd - timeCurrent) / (double)(timeEnd - timeStart) + 1e-8);
if (random < probability){
//Accept
if (minEnergy > energyNeighbor) {
#ifdef _MSC_VER
fprintf(stderr, "minEnergy updated! %.5lf -> %.5lf\n", minEnergy, energyNeighbor);
#endif
minEnergy = energyNeighbor;
result = state;
}
//fprintf(stderr, "Accepted %.5lf -> %.5lf : minEnergy=%.5lf\n", energy, energyNeighbor, minEnergy);
energy = energyNeighbor;
}
else {
//Decline
state.prev();
//fprintf(stderr, "Declined\n");
}
++counter;
}
}
fprintf(stderr, "counter:%d minEnergy:%.5lf\n", counter, minEnergy);
return result;
}
double SimulatedAnnealing::calculateProbability(double energy, double energyNeighbor, double temperature) {
if (energyNeighbor < energy) {
return 1;
}
else {
const double result = exp((energy - energyNeighbor) / (temperature + 1e-9) * 1.000);
//fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result);
return result;
}
}
//TODO:初期状態を作る関数を記述する
STATE::STATE() {
machines = initialMachines;
}
//TODO:遷移後の状態を作る関数を記述する
void STATE::next() {
if (machines.size() == 1) {
return;
}
src = xor128() % machines.size();
do {
dst = xor128() % machines.size();
} while (src == dst);
swap(machines[src], machines[dst]);
}
//TODO:遷移前の状態を作る関数を記述する
// 高々一つ前の状態までに戻れれば良い
void STATE::prev() {
if (machines.size() == 1) {
return;
}
swap(machines[src], machines[dst]);
}
//TODO:状態のエネルギーを計算する関数を記述する
// 状態はエネルギーの低い所に遷移する点に注意する
double STATE::energy() {
return -calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
}
int main() {
std::ios::sync_with_stdio(false);
int W, H;
cin >> W >> H;
cin >> N;
vector<pair<int, int> > machines;
vector<int> xs;
vector<int> ys;
REP(n, N) {
int x, y;
cin >> x >> y;
machines.push_back(MP(x, y));
xs.push_back(x);
ys.push_back(y);
}
sort(ALL(xs));
sort(ALL(ys));
vector<int> spacesX = space(xs, W);
vector<int> spacesY = space(ys, H);
CLEAR(compressedBase);
REP(x, spacesX.size()) {
REP(y, spacesY.size()) {
compressedBase[x][y] = spacesX[x] * spacesY[y];
}
}
for (auto& machine : machines) {
machine.first = distance(xs.begin(), find(ALL(xs), machine.first)) * 2 + 1;
machine.second = distance(ys.begin(), find(ALL(ys), machine.second)) * 2 + 1;
}
initialMachines = machines;
STATE state = SimulatedAnnealing().run();
cout << calculate(state.machines, compressedBase, N * 2 + 1, N * 2 + 1) << endl;
//ll bestCounter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
//bool updated = true;
//while (updated) {
// updated = false;
// for (int n = 0; n + 1 < N; ++n) {
// swap(machines[n], machines[n + 1]);
// ll counter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
// if (bestCounter < counter) {
// bestCounter = counter;
// updated = true;
// }
// else {
// swap(machines[n], machines[n + 1]);
// }
// }
//}
//cout << bestCounter << endl;
}
Submission Info
Submission Time |
|
Task |
D - 金塊ゲーム |
User |
nodchip |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
7965 Byte |
Status |
WA |
Exec Time |
3928 ms |
Memory |
1072 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
0 / 80 |
0 / 19 |
0 / 1 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt |
Subtask2 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt |
Subtask3 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt, subtask3_15.txt, subtask3_16.txt, subtask3_17.txt, subtask3_18.txt, subtask3_19.txt, subtask3_20.txt, subtask3_21.txt, subtask3_22.txt, subtask3_23.txt, subtask3_24.txt, subtask3_25.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
3923 ms |
916 KB |
sample_02.txt |
AC |
3922 ms |
932 KB |
sample_03.txt |
AC |
3921 ms |
944 KB |
subtask1_01.txt |
AC |
3923 ms |
1072 KB |
subtask1_02.txt |
AC |
3923 ms |
884 KB |
subtask1_03.txt |
AC |
3923 ms |
944 KB |
subtask1_04.txt |
AC |
3924 ms |
1068 KB |
subtask1_05.txt |
AC |
3923 ms |
928 KB |
subtask1_06.txt |
AC |
3921 ms |
928 KB |
subtask1_07.txt |
AC |
3922 ms |
784 KB |
subtask1_08.txt |
AC |
3922 ms |
932 KB |
subtask1_09.txt |
AC |
3923 ms |
1060 KB |
subtask1_10.txt |
AC |
3923 ms |
880 KB |
subtask1_11.txt |
AC |
3922 ms |
1060 KB |
subtask1_12.txt |
AC |
3921 ms |
1048 KB |
subtask1_13.txt |
AC |
3921 ms |
864 KB |
subtask1_14.txt |
WA |
3922 ms |
1056 KB |
subtask1_15.txt |
AC |
3923 ms |
956 KB |
subtask1_16.txt |
AC |
3922 ms |
1060 KB |
subtask1_17.txt |
AC |
3923 ms |
1064 KB |
subtask1_18.txt |
AC |
3924 ms |
964 KB |
subtask1_19.txt |
AC |
3923 ms |
1056 KB |
subtask1_20.txt |
AC |
3923 ms |
1060 KB |
subtask1_21.txt |
AC |
3923 ms |
1064 KB |
subtask1_22.txt |
AC |
3924 ms |
1060 KB |
subtask1_23.txt |
AC |
3922 ms |
960 KB |
subtask1_24.txt |
AC |
3923 ms |
1056 KB |
subtask1_25.txt |
AC |
3923 ms |
956 KB |
subtask2_01.txt |
AC |
3923 ms |
1060 KB |
subtask2_02.txt |
AC |
3923 ms |
864 KB |
subtask2_03.txt |
AC |
3923 ms |
960 KB |
subtask2_04.txt |
WA |
3923 ms |
1056 KB |
subtask2_05.txt |
WA |
3924 ms |
952 KB |
subtask2_06.txt |
WA |
3923 ms |
1060 KB |
subtask2_07.txt |
AC |
3922 ms |
1052 KB |
subtask2_08.txt |
AC |
3923 ms |
960 KB |
subtask2_09.txt |
WA |
3922 ms |
1048 KB |
subtask2_10.txt |
AC |
3922 ms |
944 KB |
subtask2_11.txt |
WA |
3928 ms |
1060 KB |
subtask2_12.txt |
AC |
3924 ms |
1060 KB |
subtask2_13.txt |
AC |
3924 ms |
1068 KB |
subtask2_14.txt |
AC |
3922 ms |
1044 KB |
subtask2_15.txt |
AC |
3922 ms |
956 KB |
subtask2_16.txt |
WA |
3922 ms |
1056 KB |
subtask2_17.txt |
WA |
3921 ms |
948 KB |
subtask2_18.txt |
AC |
3921 ms |
860 KB |
subtask2_19.txt |
AC |
3922 ms |
960 KB |
subtask2_20.txt |
WA |
3921 ms |
960 KB |
subtask2_21.txt |
AC |
3924 ms |
1068 KB |
subtask2_22.txt |
WA |
3924 ms |
960 KB |
subtask2_23.txt |
WA |
3923 ms |
1056 KB |
subtask2_24.txt |
WA |
3924 ms |
1064 KB |
subtask2_25.txt |
WA |
3923 ms |
956 KB |
subtask3_01.txt |
AC |
3923 ms |
924 KB |
subtask3_02.txt |
WA |
3923 ms |
928 KB |
subtask3_03.txt |
AC |
3923 ms |
928 KB |
subtask3_04.txt |
AC |
3923 ms |
1056 KB |
subtask3_05.txt |
AC |
3922 ms |
960 KB |
subtask3_06.txt |
AC |
3923 ms |
928 KB |
subtask3_07.txt |
WA |
3923 ms |
804 KB |
subtask3_08.txt |
AC |
3922 ms |
932 KB |
subtask3_09.txt |
WA |
3924 ms |
932 KB |
subtask3_10.txt |
AC |
3920 ms |
800 KB |
subtask3_11.txt |
WA |
3923 ms |
928 KB |
subtask3_12.txt |
WA |
3923 ms |
1052 KB |
subtask3_13.txt |
AC |
3922 ms |
804 KB |
subtask3_14.txt |
AC |
3921 ms |
800 KB |
subtask3_15.txt |
WA |
3922 ms |
916 KB |
subtask3_16.txt |
AC |
3923 ms |
808 KB |
subtask3_17.txt |
WA |
3921 ms |
796 KB |
subtask3_18.txt |
AC |
3923 ms |
932 KB |
subtask3_19.txt |
WA |
3923 ms |
924 KB |
subtask3_20.txt |
AC |
3921 ms |
800 KB |
subtask3_21.txt |
AC |
3923 ms |
920 KB |
subtask3_22.txt |
WA |
3922 ms |
920 KB |
subtask3_23.txt |
AC |
3922 ms |
928 KB |
subtask3_24.txt |
AC |
3921 ms |
928 KB |
subtask3_25.txt |
WA |
3924 ms |
920 KB |