Submission #1871488
Source Code Expand
#include <vector>
#include <cfloat>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <string>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cassert>
#include <random>
#include <queue>
#include <list>
#include <map>
#include <array>
#include <chrono>
using namespace std;
typedef long long ll;
vector<int>connect[600];
vector<pair<int,int> >node[600];
vector<pair<int,int> >edgeList;
int dummy_score;
int ans[600];
int memo[65][65];
int SZ;
int V;
int E;
int edge[600][600];
int vertex[30000][2];
int V_emb;
int E_emb;
int emb_edge[3605][3605];
int calc_score();
void SA();
ll make_rand();
void gen_rand_next_state(int iter);
double gen_per_rand(const ll res = 1LL << 60) {
return 1.0 * (make_rand() % res) / (res - 1);
}
double probability(double e1, double e2, double t) {
if (e1 <= e2) {
return 1;
}
else {
double res = exp((-e1 + e2) / t);
return res;
}
}
chrono::system_clock::time_point start;
int main(){
start = chrono::system_clock::now();
scanf("%d %d",&V,&E);
int u,v,w;
int i;
for(i=0;i<E;i++){
scanf("%d %d %d",&u,&v,&w);
edge[u][v]=w;
edge[v][u]=w;
vertex[i][0]=u;
vertex[i][1]=v;
connect[u].push_back(v);
connect[v].push_back(u);
node[u].push_back(make_pair(w,v));
node[v].push_back(make_pair(w,u));
}
scanf("%d %d",&V_emb,&E_emb);
for(i=0;i<E_emb;i++){
scanf("%d %d",&u,&v);
emb_edge[u][v]=1;
emb_edge[v][u]=1;
}
for(i=2;i<=100;i++){
if(i*i==V_emb){
SZ=i;
break;
}
}
int N=(int) sqrt(V_emb) + 2;
int n=(int) ceil(sqrt(V));
int offset=(N-n)/2;
int y=offset;
int x=offset;
for(i=1;i<=V;i++){
int z=(y*N)+x;
ans[i]=z;
x++;
if (x == n + offset) {
x = offset;
y++;
}
}
for (i = 1; i <= V; i++) {
int z = ans[i];
y = z / N - 1;
x = z % N - 1;
int zz=y * (N - 2) + x + 1;
ans[i]= zz;
memo[(zz-1)/SZ][(zz-1)%SZ]=i;
}
for(i=1;i<=V;i++){
sort(node[i].begin(),node[i].end());
reverse(node[i].begin(),node[i].end());
int limit = max(12, (int) (node[i].size() * 0.15));
for(int k=0;k<limit;k++){
if(k>=node[i].size()){break;}
for (int j = 0; j < node[i][k].first; j++) {
edgeList.push_back(make_pair(i,node[i][k].second));
edgeList.push_back(make_pair(node[i][k].second,i));
}
}
}
random_shuffle(edgeList.begin(),edgeList.end());
SA();
return 0;
}
int calc_score(){
int score=0;
int i;
for(i=0;i<E;i++){
if(emb_edge[ans[vertex[i][0]]][ans[vertex[i][1]]]==1){
score+=edge[vertex[i][0]][vertex[i][1]];
}
}
return score;
}
void gen_rand_next_state(int iter) {
int i,j;
int score=dummy_score;
int t=ans[edgeList[iter].first];
int end_point=edgeList[iter].second;
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={-1,-1,-1,0,0,1,1,1};
int dd[8]={-SZ-1,-SZ,-SZ+1,-1,1,SZ-1,SZ,SZ+1};
int x=(ans[end_point]-1)%SZ;
int y=(ans[end_point]-1)/SZ;
int r;
while(1){
r=make_rand()%8;
if(0<=x+dx[r]&&x+dx[r]<SZ&&0<=y+dy[r]&&y+dy[r]<SZ){
if(t!=ans[end_point]+dd[r]){
break;
}
}
}
if(memo[y+dy[r]][x+dx[r]]>0){
int a=end_point;
int b=memo[y+dy[r]][x+dx[r]];
for(j=0;j<connect[a].size();j++){
if(emb_edge[ans[a]][ans[connect[a][j]]]==1 && connect[a][j]!=b){
score-=edge[a][connect[a][j]];
}
if(emb_edge[ans[b]][ans[connect[a][j]]]==1 && connect[a][j]!=b){
score+=edge[a][connect[a][j]];
}
}
for(j=0;j<connect[b].size();j++){
if(emb_edge[ans[b]][ans[connect[b][j]]]==1 && connect[b][j]!=a){
score-=edge[b][connect[b][j]];
}
if(emb_edge[ans[a]][ans[connect[b][j]]]==1 && connect[b][j]!=a){
score+=edge[b][connect[b][j]];
}
}
swap(memo[y][x],memo[y+dy[r]][x+dx[r]]);
swap(ans[a],ans[b]);
dummy_score=score;
}
else{
int a=end_point;
int b=((y+dy[r])*SZ)+(x+dx[r])+1;
for(j=0;j<connect[a].size();j++){
if(emb_edge[ans[a]][ans[connect[a][j]]]==1){
score-=edge[a][connect[a][j]];
}
if(emb_edge[b][ans[connect[a][j]]]==1){
score+=edge[a][connect[a][j]];
}
}
int t=memo[y][x];
memo[y][x]=0;
memo[y+dy[r]][x+dx[r]]=t;
ans[a]=b;
dummy_score=score;
}
}
ll make_rand() {
static ll x = 123456789;
static ll y = 362436069;
static ll z = 521288629;
static ll w = 88675123;
ll t;
t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
void SA(){
int c_field[600];
memcpy(c_field, ans, sizeof(ans));
int c_score = calc_score();
dummy_score=c_score;
int b_field[600];
memcpy(b_field, c_field, sizeof(c_field));
int b_score = c_score;
double param1, param2;
double diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
double simulate_time = (9.99 - diff)*1000.0;
param1 = 1.0 / (simulate_time / 2.2);
param2 = 1.0 / exp(2.2);
int n_field[600];
int n_memo[65][65];
int iter=0;
while (1) {
//if (iter % 1000 == 0) {
// cout << iter << " " << c_score << endl;
//}
// 時間になったので打ち切り
diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
if (diff > 9.99) {
break;
}
memcpy(n_field,ans,sizeof(ans));
memcpy(n_memo,memo,sizeof(memo));
int temp_score=dummy_score;
gen_rand_next_state(iter%edgeList.size());
int n_score = dummy_score;
// 最高の値を更新
if (n_score > b_score) {
memcpy(b_field, ans, sizeof(ans));
b_score = n_score;
}
// 状態遷移するか判定
if (gen_per_rand() <= probability(c_score, n_score, 5.0 * exp((9.99 - diff) * param1*1000.0) * param2)) {
c_score = n_score;
}
else{
memcpy(ans,n_field,sizeof(n_field));
memcpy(memo,n_memo,sizeof(n_memo));
dummy_score=temp_score;
}
iter++;
}
//cout << "best_score : " << b_score << endl;
int i;
for (i = 1; i <= V; i++) {
printf("%d %d\n",i,b_field[i]);
}
}
Submission Info
Submission Time |
|
Task |
A - Problem 1 |
User |
tekitouk |
Language |
C++14 (GCC 5.4.1) |
Score |
137097 |
Code Size |
6155 Byte |
Status |
AC |
Exec Time |
9993 ms |
Memory |
54004 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:65:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&V,&E);
^
./Main.cpp:72:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&u,&v,&w);
^
./Main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&V_emb,&E_emb);
^
./Main.cpp:86:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u,&v);
^
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 |
1658 / 1000000 |
8417 / 1000000 |
10332 / 1000000 |
6081 / 1000000 |
1196 / 1000000 |
8699 / 1000000 |
8395 / 1000000 |
5709 / 1000000 |
6433 / 1000000 |
7039 / 1000000 |
4489 / 1000000 |
129 / 1000000 |
2089 / 1000000 |
4375 / 1000000 |
8222 / 1000000 |
1738 / 1000000 |
3727 / 1000000 |
4027 / 1000000 |
3987 / 1000000 |
1877 / 1000000 |
3775 / 1000000 |
3144 / 1000000 |
5280 / 1000000 |
2138 / 1000000 |
2760 / 1000000 |
1684 / 1000000 |
10857 / 1000000 |
8683 / 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 |
9992 ms |
2432 KB |
00_sample_01 |
AC |
9992 ms |
2688 KB |
10_random_00 |
AC |
9992 ms |
5248 KB |
10_random_01 |
AC |
9992 ms |
8180 KB |
10_random_02 |
AC |
9993 ms |
49656 KB |
10_random_03 |
AC |
9992 ms |
16892 KB |
10_random_04 |
AC |
9992 ms |
2944 KB |
10_random_05 |
AC |
9993 ms |
23552 KB |
10_random_06 |
AC |
9992 ms |
15228 KB |
10_random_07 |
AC |
9992 ms |
37240 KB |
10_random_08 |
AC |
9992 ms |
10744 KB |
20_full_00 |
AC |
9992 ms |
11000 KB |
20_full_01 |
AC |
9992 ms |
14080 KB |
20_full_02 |
AC |
9992 ms |
2432 KB |
20_full_03 |
AC |
9992 ms |
13572 KB |
20_full_04 |
AC |
9992 ms |
5888 KB |
20_full_05 |
AC |
9992 ms |
10104 KB |
20_full_06 |
AC |
9992 ms |
21760 KB |
20_full_07 |
AC |
9992 ms |
7812 KB |
20_full_08 |
AC |
9992 ms |
3716 KB |
30_sparse_00 |
AC |
9993 ms |
26880 KB |
30_sparse_01 |
AC |
9992 ms |
5376 KB |
30_sparse_02 |
AC |
9993 ms |
22784 KB |
30_sparse_03 |
AC |
9992 ms |
22528 KB |
30_sparse_04 |
AC |
9992 ms |
10620 KB |
30_sparse_05 |
AC |
9992 ms |
22144 KB |
30_sparse_06 |
AC |
9993 ms |
45056 KB |
30_sparse_07 |
AC |
9992 ms |
11520 KB |
60_random_max_00 |
AC |
9993 ms |
54004 KB |
70_full_max_00 |
AC |
9993 ms |
28532 KB |