Submission #1872702
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
unsigned int xor128(){
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));
}
class Timer {
double start_time;
double GetNow(){
unsigned long long a, d;
__asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
#ifdef LOCAL
return (d << 32 | a) / 3400000000.0;
#else
return (d << 32 | a) / 2800000000.0;
#endif
}
public:
void Start(){
start_time = GetNow();
}
double GetSec(){
return GetNow()-start_time;
}
};
template<int MAX_V, int MAX_N>
class SA {
const double kTimeLimit = 29.9;
const int kVx[8] = {-1,0,1,1,1,0,-1,-1};
const int kVy[8] = {1,1,1,0,-1,-1,-1,0};
Timer timer;
int g_v, g_e;
int gemb_v, gemb_e, gemb_n;
int g[MAX_V][MAX_V];
int gemb_score;
int gemb[MAX_N][MAX_N];
int best_gemb_score;
int best_gemb[MAX_N][MAX_N];
int sg[MAX_V][MAX_V];
int sgemb[MAX_N][MAX_N];
int save_y, save_x;
int save_before, save_after;
//mt19937 mt;
//uniform_real_distribution<double> urd;
inline bool InRange(int y, int x){
return 0 <= y && y < gemb_n && 0 <= x && x < gemb_n;
}
double Frand() {
return xor128()%UINT_MAX/static_cast<double>(UINT_MAX);
//return urd(mt);
}
void UpdateBestGemb(){
best_gemb_score = gemb_score;
rep(i,gemb_n){
rep(j,gemb_n){
best_gemb[i][j] = gemb[i][j];
}
}
}
// Gembの初期状態を作成する
void InitGemb(){
vector<bool> can_move(g_v, true);
vector<int> pos(g_v, -1);
// ランダムに配置
/*
rep(i,g_v){
while(true){
int r = mt() % gemb_v;
int y = r / gemb_n;
int x = r % gemb_n;
if(gemb[y][x] == -1){
gemb[y][x] = i;
pos[i] = r;
break;
}
}
}
*/
int cnt_max = 0;
rep(i,g_v){
int cnt = 0;
rep(j,g_v){
if(g[i][j] >= 0) cnt++;
}
cnt_max = max(cnt_max, cnt);
}
// できるだけ隣接頂点を近くに配置
int window_size = 5;
while(true){
int num_cell = (window_size*2)*(window_size*2);
if(num_cell * 0.5 > cnt_max) break;
window_size++;
}
rep(i,g_v){
int r, y, x;
if(pos[i] == -1){
while(true){
r = xor128() % gemb_v;
y = r / gemb_n;
x = r % gemb_n;
if(gemb[y][x] == -1){
gemb[y][x] = i;
pos[i] = r;
break;
}
}
}else{
r = pos[i];
y = r / gemb_n;
x = r % gemb_n;
}
// iに隣接する頂点をiの近くに配置
rep(j,g_v) if(g[i][j] >= 0 && pos[j] == -1){
int iter = 1000;
while(--iter){
int cand_y = y + xor128() % (window_size * 2) - window_size;
int cand_x = x + xor128() % (window_size * 2) - window_size;
if(!InRange(cand_y,cand_x)) continue;
if(gemb[cand_y][cand_x] != -1) continue;
gemb[cand_y][cand_x] = j;
pos[j] = cand_y * gemb_n + cand_x;
break;
}
}
}
// 頂点を適当に伸ばせるだけ伸ばす
bool flg = true;
int num_non = g_v;
while(flg){
flg = false;
rep(i,g_v) if(can_move[i]){
int p = pos[i];
int y = p / gemb_n;
int x = p % gemb_n;
vector<int> ok;
rep(k,8){
int ny = y + kVy[k];
int nx = x + kVx[k];
if(!InRange(ny, nx)) continue;
if(gemb[ny][nx] != -1) continue;
ok.push_back(k);
}
if(ok.size() == 0){
can_move[i] = false;
}else{
int rk = xor128() % (ok.size());
int ny = y + kVy[ok[rk]];
int nx = x + kVx[ok[rk]];
gemb[ny][nx] = i;
pos[i] = ny * gemb_n + nx;
num_non++;
flg = true;
}
}
}
#ifdef LOCAL
rep(i,gemb_n){
rep(j,gemb_n){
fprintf(stderr, "%4d", gemb[i][j]);
}
fprintf(stderr, "\n");
}
#endif
/*
int cnt = 0;
rep(i,gemb_n){
rep(j,gemb_n){
best_gemb[i][j] = gemb[i][j] = cnt++;
if(cnt >= g_v) break;
}
if(cnt >= g_v) break;
}
*/
UpdateBestGemb();
gemb_score = CalcScore();
cerr << "FirstScore: " << gemb_score << endl;
}
// Gembの現状態の近傍の状態へ更新する
int MoveNeighbor(){
save_y = save_x = -1;
int r = xor128() % gemb_v;
int y = r / gemb_n;
int x = r % gemb_n;
int k = xor128() % 8;
int ny = y + kVy[k];
int nx = x + kVx[k];
if(!InRange(ny, nx)) return 0;
if(gemb[y][x] == -1 && gemb[ny][nx] == -1) return 0;
int before_score = gemb_score;
save_y = ny;
save_x = nx;
save_before = gemb[ny][nx];
save_after = gemb[y][x];
gemb[ny][nx] = gemb[y][x];
int after_score = CalcScore();
gemb_score = after_score;
return after_score - before_score;
}
// ひとつ前の状態に戻す
void MoveUndo(int delta){
gemb_score -= delta;
if(save_y < 0) return;
gemb[save_y][save_x] = save_before;
}
// 温度の更新
double CalcTemp(double sec, double T){
//return T * 0.999;
return 120.0 * pow(0.4, sec);
}
// 反復回数の更新
int CalcLen(double sec, int R){
//return R;
//return -29 * sec + 300;
//if(sec < kTimeLimit/2) return 200;
if(sec < kTimeLimit*4/5.0) return 200;
else return 10;
}
// スコア計算
int CalcScore(){
rep(i,MAX_N) rep(j,MAX_N) sgemb[i][j] = -1;
rep(i,MAX_V) rep(j,MAX_V) sg[i][j] = -1;
vector<int> cnt(MAX_V,0);
rep(i,gemb_n){
rep(j,gemb_n){
if(gemb[i][j] == -1) continue;
if(sgemb[i][j] != -1) continue;
if(cnt[gemb[i][j]] != 0) return 0;
queue<pair<int,int>> que;
que.push(make_pair(i,j));
while(!que.empty()){
pair<int,int> p = que.front(); que.pop();
if(sgemb[p.first][p.second] != -1) continue;
if(gemb[p.first][p.second] != gemb[i][j]) continue;
sgemb[p.first][p.second] = gemb[i][j];
cnt[gemb[i][j]]++;
rep(k,8){
int ny = p.first + kVy[k];
int nx = p.second + kVx[k];
if(!InRange(ny,nx)) continue;
if(sgemb[ny][nx] != -1) continue;
if(gemb[p.first][p.second] != gemb[ny][nx]){
if(g[gemb[p.first][p.second]][gemb[ny][nx]] >= 0){
sg[gemb[p.first][p.second]][gemb[ny][nx]] = g[gemb[p.first][p.second]][gemb[ny][nx]];
sg[gemb[ny][nx]][gemb[p.first][p.second]] = g[gemb[p.first][p.second]][gemb[ny][nx]];
}
}else{
que.push(make_pair(ny,nx));
}
}
}
}
}
int add_score = 0;
int loss_score = 0;
int bonus_score = 100000;
rep(i,g_v){
if(cnt[i] == 0) return 0;
loss_score -= cnt[i]-1;
rep(j,g_v){
if(g[i][j] >= 0 && sg[i][j] != g[i][j]){
bonus_score = 0;
}
if(sg[i][j] == -1) continue;
add_score += sg[i][j];
}
}
add_score /= 2;
return 5000 + add_score + loss_score + bonus_score;
}
public:
//SA():mt(random_device()()){
SA(){
timer.Start();
Init();
}
void Init(){
rep(i,MAX_V) rep(j,MAX_V) g[i][j] = -1;
rep(i,MAX_N) rep(j,MAX_N) best_gemb[i][j] = gemb[i][j] = -1;
gemb_score = 0;
best_gemb_score = -1;
}
void SetGve(int V, int E){
g_v = V;
g_e = E;
}
void SetEmbve(int V, int E){
gemb_v = V;
gemb_e = E;
gemb_n = (int)sqrt(V);
assert(gemb_n * gemb_n == gemb_v);
}
void SetG(int u, int v){
g[u][v] = 100;
g[v][u] = 100;
}
void Solve(){
// 初期解
InitGemb();
double sec = timer.GetSec();
// 初期パラメータ
double T = CalcTemp(sec, 150);
int R = CalcLen(sec, 10);
int cnt = 0;
while(true){
sec = timer.GetSec();
if(sec > kTimeLimit) break;
//if(T < 0.005) break;
rep(i,R){
// 近傍移動
int delta = MoveNeighbor();
// 受理するかどうか
if(gemb_score == 0){ // 受理しない
MoveUndo(delta);
}else if(delta >= 0){ // 受理する
;
}else{
if(exp(delta / T) >= Frand()){ // 受理する
;
}else{ // 受理しない
MoveUndo(delta);
}
}
// ベスト解を記録
if(best_gemb_score < gemb_score){
UpdateBestGemb();
}
cnt++;
}
/*
cerr << sec << "\t" << best_gemb_score << "\t" << gemb_score << "\t" << T << endl;
if(cnt % 10000 == 0){
rep(i,gemb_n){
rep(j,gemb_n){
fprintf(stderr, "%4d", best_gemb[i][j]);
}
fprintf(stderr, "\n");
}
}
*/
T = CalcTemp(sec, T);
R = CalcLen(sec, R);
}
}
void PrintResult(){
map<int,vector<int>> ret;
rep(i,gemb_n){
rep(j,gemb_n){
if(best_gemb[i][j] != -1){
int g_p = best_gemb[i][j];
int gemb_p = i * gemb_n + j;
ret[g_p+1].push_back(gemb_p+1);
}
}
}
FOR(it,ret){
cout << (it->second).size();
rep(i,(it->second).size()){
cout << " " << (it->second)[i];
}
cout << endl;
}
cerr << "BestScore: " << best_gemb_score << endl;
#ifdef LOCAL
rep(i,gemb_n){
rep(j,gemb_n){
fprintf(stderr, "%4d", best_gemb[i][j]);
}
fprintf(stderr, "\n");
}
#endif
}
};
int main(){
SA<500,65> sa;
int G_V, G_E;
cin >> G_V >> G_E;
sa.SetGve(G_V, G_E);
rep(i,G_E){
int u, v;
cin >> u >> v;
u--;
v--;
sa.SetG(u, v);
}
int Gemb_V, Gemb_E;
cin >> Gemb_V >> Gemb_E;
sa.SetEmbve(Gemb_V, Gemb_E);
rep(i,Gemb_E){
int a, b;
cin >> a >> b;
}
sa.Solve();
sa.PrintResult();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Problem 2 |
User |
phyllo |
Language |
C++14 (GCC 5.4.1) |
Score |
1659707 |
Code Size |
10881 Byte |
Status |
AC |
Exec Time |
29980 ms |
Memory |
2816 KB |
Judge Result
Set Name |
sample_00 |
sample_01 |
random_00 |
random_01 |
random_02 |
random_03 |
random_04 |
random_05 |
random_06 |
random_07 |
random_08 |
random_09 |
random_10 |
random_11 |
random_12 |
random_13 |
random_14 |
random_15 |
random_16 |
random_17 |
random_18 |
random_19 |
random_20 |
random_21 |
random_22 |
random_23 |
random_24 |
random_25 |
random_26 |
random_27 |
Score / Max Score |
106382 / 1000000 |
7394 / 1000000 |
28277 / 1000000 |
33272 / 1000000 |
6594 / 1000000 |
47398 / 1000000 |
19689 / 1000000 |
108211 / 1000000 |
73971 / 1000000 |
28996 / 1000000 |
42798 / 1000000 |
76843 / 1000000 |
91816 / 1000000 |
17481 / 1000000 |
52318 / 1000000 |
98952 / 1000000 |
100415 / 1000000 |
80821 / 1000000 |
44442 / 1000000 |
49861 / 1000000 |
26296 / 1000000 |
72536 / 1000000 |
74176 / 1000000 |
44210 / 1000000 |
79628 / 1000000 |
34180 / 1000000 |
27686 / 1000000 |
16289 / 1000000 |
88211 / 1000000 |
80564 / 1000000 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
sample_00 |
00_sample_00 |
sample_01 |
00_sample_01 |
random_00 |
10_random_00 |
random_01 |
10_random_01 |
random_02 |
10_random_02 |
random_03 |
10_random_03 |
random_04 |
10_random_04 |
random_05 |
10_random_05 |
random_06 |
10_random_06 |
random_07 |
10_random_07 |
random_08 |
10_random_08 |
random_09 |
10_random_09 |
random_10 |
10_random_10 |
random_11 |
10_random_11 |
random_12 |
10_random_12 |
random_13 |
10_random_13 |
random_14 |
10_random_14 |
random_15 |
10_random_15 |
random_16 |
10_random_16 |
random_17 |
10_random_17 |
random_18 |
10_random_18 |
random_19 |
10_random_19 |
random_20 |
10_random_20 |
random_21 |
10_random_21 |
random_22 |
10_random_22 |
random_23 |
10_random_23 |
random_24 |
10_random_24 |
random_25 |
10_random_25 |
random_26 |
10_random_26 |
random_27 |
10_random_27 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
29974 ms |
2816 KB |
00_sample_01 |
AC |
29974 ms |
2560 KB |
10_random_00 |
AC |
29974 ms |
2304 KB |
10_random_01 |
AC |
29975 ms |
2304 KB |
10_random_02 |
AC |
29974 ms |
2304 KB |
10_random_03 |
AC |
29977 ms |
2304 KB |
10_random_04 |
AC |
29974 ms |
2304 KB |
10_random_05 |
AC |
29975 ms |
2304 KB |
10_random_06 |
AC |
29976 ms |
2304 KB |
10_random_07 |
AC |
29977 ms |
2304 KB |
10_random_08 |
AC |
29975 ms |
2304 KB |
10_random_09 |
AC |
29976 ms |
2304 KB |
10_random_10 |
AC |
29977 ms |
2304 KB |
10_random_11 |
AC |
29974 ms |
2304 KB |
10_random_12 |
AC |
29975 ms |
2304 KB |
10_random_13 |
AC |
29975 ms |
2304 KB |
10_random_14 |
AC |
29975 ms |
2304 KB |
10_random_15 |
AC |
29976 ms |
2304 KB |
10_random_16 |
AC |
29975 ms |
2304 KB |
10_random_17 |
AC |
29980 ms |
2304 KB |
10_random_18 |
AC |
29974 ms |
2304 KB |
10_random_19 |
AC |
29975 ms |
2304 KB |
10_random_20 |
AC |
29974 ms |
2304 KB |
10_random_21 |
AC |
29978 ms |
2304 KB |
10_random_22 |
AC |
29978 ms |
2304 KB |
10_random_23 |
AC |
29975 ms |
2304 KB |
10_random_24 |
AC |
29975 ms |
2304 KB |
10_random_25 |
AC |
29974 ms |
2304 KB |
10_random_26 |
AC |
29975 ms |
2304 KB |
10_random_27 |
AC |
29976 ms |
2304 KB |