Submission #2091655
Source Code Expand
#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define REP(i,n) for (int i = 0; i < n; i++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
struct Timer {
double CYCLE_PER_SEC = 2800000000.0;
unsigned long long BEGIN_CYCLE = 0;
unsigned long long int getCycle() {
unsigned int low, high;
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}
void start(void) {
BEGIN_CYCLE = getCycle();
}
double get_time(void) {
return (double)(getCycle() - BEGIN_CYCLE) / CYCLE_PER_SEC;
}
};
struct XorShift {
unsigned int x;
XorShift () : x(2463534242U) {}
unsigned int rand() {
x ^= (x << 13);
x ^= (x >> 17);
x ^= (x << 5);
return x;
}
};
vector < int > get_order(int Vemb, int Vori) {
vector < pair < int, int > > d;
REP(i,25) {
if ((i & 1) == 0) {
REP(j, i + 1) d.push_back(make_pair(1, 0));
REP(j, i + 1) d.push_back(make_pair(0, 1));
} else {
REP(j, i + 1) d.push_back(make_pair(-1, 0));
REP(j, i + 1) d.push_back(make_pair(0, -1));
}
}
int sq = sqrt(Vemb);
int x = (sq - 1) >> 1;
int y = (sq - 1) >> 1;
vector < int > ret;
REP(i,Vori) {
ret.push_back(x * sq + y);
x += d[i].first;
y += d[i].second;
}
return ret;
}
/************************************************/
constexpr int REFRESH_NUM = 6;
constexpr double TIME_LIMIT = 4.50;
constexpr double TEMP_START = 4.20;
constexpr double TEMP_END = 0.30;
constexpr double TEMP_DIFF = (TEMP_START - TEMP_END) / TIME_LIMIT;
int Vori, Eori;
int Vemb, Eemb;
char w_ori[512][512];
short Gemb[3610][8];
char GMemb[3610][3610];
int Gemb_size[3610];
int used[3610];
int emp_num;
int emp_pos[3610];
int point_score[512];
int Score;
int BestScore;
int Answer[512];
int BestAnswer[512];
XorShift Random;
/************************************************/
int score_diff(int idx1, int idx2) {
int ret = - point_score[idx1] - point_score[idx2];
int v1 = Answer[idx1];
int v2 = Answer[idx2];
REP(i,8) ret += w_ori[idx2][used[Gemb[v1][i]]];
REP(i,8) ret += w_ori[idx1][used[Gemb[v2][i]]];
if (GMemb[v1][v2]) ret += w_ori[idx1][idx2] << 1;
return ret;
}
int score_diff_swap(int idx1, int idx2) {
int ret = - point_score[idx1];
int v2 = emp_pos[idx2];
REP(i,8) ret += w_ori[idx1][used[Gemb[v2][i]]];
return ret;
}
bool prob(int diff, double temp) {
if (diff >= 0) return true;
if (diff < -18) return false;
double P = exp((double) diff / temp) * 4294967295.0;
return Random.rand() < P;
}
void update1(int idx1, int idx2, int diff) {
int v1 = Answer[idx1];
int v2 = Answer[idx2];
point_score[idx1] = 0;
point_score[idx2] = 0;
REP(i,8) {
int opp = used[Gemb[v2][i]];
point_score[idx1] += w_ori[idx1][opp];
}
REP(i,8) {
int opp = used[Gemb[v2][i]];
point_score[opp ] += w_ori[idx1][opp];
}
REP(i,8) {
int opp = used[Gemb[v2][i]];
point_score[opp ] -= w_ori[idx2][opp];
}
REP(i,8) {
int opp = used[Gemb[v1][i]];
point_score[idx2] += w_ori[idx2][opp];
}
REP(i,8) {
int opp = used[Gemb[v1][i]];
point_score[opp ] += w_ori[idx2][opp];
}
REP(i,8) {
int opp = used[Gemb[v1][i]];
point_score[opp ] -= w_ori[idx1][opp];
}
if (GMemb[v1][v2]) {
point_score[idx1] += w_ori[idx1][idx2] << 1;
point_score[idx2] += w_ori[idx1][idx2] << 1;
}
swap(Answer[idx1], Answer[idx2]);
swap(used[v1], used[v2]);
Score += diff;
if (BestScore < Score) {
BestScore = Score;
copy(Answer, Answer + Vori, BestAnswer);
}
}
void update2(int idx1, int idx2, int diff) {
int v1 = Answer[idx1];
int v2 = emp_pos[idx2];
point_score[idx1] = 0;
REP(i,8) {
int opp = used[Gemb[v1][i]];
point_score[opp ] -= w_ori[idx1][opp];
}
REP(i,8) {
int opp = used[Gemb[v2][i]];
point_score[idx1] +=w_ori[idx1][opp];
}
REP(i,8) {
int opp = used[Gemb[v2][i]];
point_score[opp ] += w_ori[idx1][opp];
}
swap(Answer[idx1], emp_pos[idx2]);
swap(used[v1], used[v2]);
Score += diff;
if (BestScore < Score) {
BestScore = Score;
copy(Answer, Answer + Vori, BestAnswer);
}
}
void annealing1(double temp) {
REP(idx1,Vori) {
int idx2 = Random.rand() % Vori;
if (idx1 == idx2) continue;
int diff = score_diff(idx1, idx2);
if (prob(diff, temp)) {
update1(idx1, idx2, diff);
}
}
}
void annealing2(double temp) {
REP(idx1,Vori) {
int idx2 = Random.rand() % emp_num;
int diff = score_diff_swap(idx1, idx2);
if (prob(diff, temp)) {
update2(idx1, idx2, diff);
}
}
}
/************************************************/
int get_point_score(int v, int ans_idx) {
int ret = 0;
REP(i,8) ret += w_ori[ans_idx][used[Gemb[v][i]]];
return ret;
}
void set_emp_pos() {
Score = BestScore;
copy(BestAnswer, BestAnswer + Vori, Answer);
fill(used, used + 3610, 501);
REP(i,Vori) used[Answer[i]] = i;
fill (point_score, point_score + 512, 0);
REP(i,Vori) REP(j,8) {
int nv = Gemb[Answer[i]][j];
point_score[i] += w_ori[i][used[nv]];
}
emp_num = 0;
REP(i,Vemb) if (used[i] == 501) {
int cnt = 0;
REP(j,8) if (used[Gemb[i][j]] != 501) cnt++;
if (cnt > 2) emp_pos[emp_num++] = i;
}
}
void greedy() {
vector < int > order = get_order(Vemb, Vori);
REP(i,Vori) {
int idx = Random.rand() % Vori;
if (i != 0) {
int diff = -1;
REP(j,Vori) if (Answer[j] < 0) {
int difft = get_point_score(order[i], j);
if (diff < difft) {
diff = difft;
idx = j;
}
}
}
Answer[idx] = order[i];
used[order[i]] = idx;
}
fill (point_score, point_score + 512, 0);
REP(i,Vori) REP(j,8) {
int nv = Gemb[Answer[i]][j];
Score += w_ori[i][used[nv]];
point_score[i] += w_ori[i][used[nv]];
}
Score >>= 1;
BestScore = Score;
copy(Answer, Answer + Vori, BestAnswer);
}
/************************************************/
void initialize() {
Score = 0;
BestScore = Score;
fill(used, used + 3610, 501);
fill(Answer, Answer + 512, -1);
}
int main() {
Timer timer;
timer.start();
REP(i,3610) fill(Gemb[i], Gemb[i] + 8, 3601);
scanf("%d%d", &Vori, &Eori);
REP(i,Eori) {
int a,b,wt;
scanf("%d%d%d", &a, &b, &wt);
a--, b--;
w_ori[a][b] = wt;
w_ori[b][a] = wt;
}
scanf("%d%d", &Vemb, &Eemb);
REP(i,Eemb) {
int a,b;
scanf("%d%d", &a, &b);
a--, b--;
GMemb[a][b] = 1;
GMemb[b][a] = 1;
Gemb[a][Gemb_size[a]++] = b;
Gemb[b][Gemb_size[b]++] = a;
}
initialize();
greedy();
REP(i,REFRESH_NUM) {
set_emp_pos();
double limit = (double)(i + 1) / (double) REFRESH_NUM * TIME_LIMIT;
while (true) {
annealing1(TEMP_START - TEMP_DIFF * timer.get_time());
annealing2(TEMP_START - TEMP_DIFF * timer.get_time());
if (timer.get_time() > limit) break;
}
}
timer.start();
REP(i,REFRESH_NUM) {
set_emp_pos();
double limit = (double)(i + 1) / (double) REFRESH_NUM * TIME_LIMIT;
while (true) {
annealing1(TEMP_START - TEMP_DIFF * timer.get_time());
annealing2(TEMP_START - TEMP_DIFF * timer.get_time());
if (timer.get_time() > limit) break;
}
}
REP(i,Vori) {
printf("%d %d\n", i + 1, BestAnswer[i] + 1);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Problem 1 |
User |
kosakkun |
Language |
C++14 (GCC 5.4.1) |
Score |
161328 |
Code Size |
8531 Byte |
Status |
AC |
Exec Time |
9023 ms |
Memory |
12928 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:272:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &Vori, &Eori);
^
./Main.cpp:275:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &wt);
^
./Main.cpp:281:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &Vemb, &Eemb);
^
./Main.cpp:284:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
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 |
full_00 |
full_01 |
full_02 |
full_03 |
full_04 |
full_05 |
full_06 |
full_07 |
full_08 |
sparse_00 |
sparse_01 |
sparse_02 |
sparse_03 |
sparse_04 |
sparse_05 |
sparse_06 |
sparse_07 |
random_max |
full_max |
Score / Max Score |
7 / 1000000 |
150 / 1000000 |
1692 / 1000000 |
9511 / 1000000 |
14650 / 1000000 |
6585 / 1000000 |
1259 / 1000000 |
10840 / 1000000 |
9892 / 1000000 |
6248 / 1000000 |
7078 / 1000000 |
7559 / 1000000 |
4828 / 1000000 |
129 / 1000000 |
2175 / 1000000 |
4609 / 1000000 |
8902 / 1000000 |
1816 / 1000000 |
3940 / 1000000 |
4275 / 1000000 |
4960 / 1000000 |
2083 / 1000000 |
4501 / 1000000 |
3870 / 1000000 |
6703 / 1000000 |
2466 / 1000000 |
3904 / 1000000 |
1905 / 1000000 |
15450 / 1000000 |
9341 / 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 |
full_00 |
20_full_00 |
full_01 |
20_full_01 |
full_02 |
20_full_02 |
full_03 |
20_full_03 |
full_04 |
20_full_04 |
full_05 |
20_full_05 |
full_06 |
20_full_06 |
full_07 |
20_full_07 |
full_08 |
20_full_08 |
sparse_00 |
30_sparse_00 |
sparse_01 |
30_sparse_01 |
sparse_02 |
30_sparse_02 |
sparse_03 |
30_sparse_03 |
sparse_04 |
30_sparse_04 |
sparse_05 |
30_sparse_05 |
sparse_06 |
30_sparse_06 |
sparse_07 |
30_sparse_07 |
random_max |
60_random_max_00 |
full_max |
70_full_max_00 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
9023 ms |
384 KB |
00_sample_01 |
AC |
9023 ms |
896 KB |
10_random_00 |
AC |
9023 ms |
1280 KB |
10_random_01 |
AC |
9023 ms |
1536 KB |
10_random_02 |
AC |
9023 ms |
12800 KB |
10_random_03 |
AC |
9023 ms |
4480 KB |
10_random_04 |
AC |
9023 ms |
640 KB |
10_random_05 |
AC |
9023 ms |
6656 KB |
10_random_06 |
AC |
9023 ms |
4480 KB |
10_random_07 |
AC |
9023 ms |
10624 KB |
10_random_08 |
AC |
9023 ms |
2176 KB |
20_full_00 |
AC |
9023 ms |
2304 KB |
20_full_01 |
AC |
9023 ms |
4480 KB |
20_full_02 |
AC |
9023 ms |
512 KB |
20_full_03 |
AC |
9023 ms |
4352 KB |
20_full_04 |
AC |
9023 ms |
1024 KB |
20_full_05 |
AC |
9023 ms |
1536 KB |
20_full_06 |
AC |
9023 ms |
6400 KB |
20_full_07 |
AC |
9023 ms |
1664 KB |
20_full_08 |
AC |
9023 ms |
768 KB |
30_sparse_00 |
AC |
9023 ms |
6656 KB |
30_sparse_01 |
AC |
9023 ms |
1408 KB |
30_sparse_02 |
AC |
9023 ms |
6656 KB |
30_sparse_03 |
AC |
9023 ms |
6656 KB |
30_sparse_04 |
AC |
9023 ms |
2432 KB |
30_sparse_05 |
AC |
9023 ms |
6528 KB |
30_sparse_06 |
AC |
9023 ms |
12800 KB |
30_sparse_07 |
AC |
9023 ms |
4480 KB |
60_random_max_00 |
AC |
9023 ms |
12928 KB |
70_full_max_00 |
AC |
9023 ms |
6528 KB |