Submission #2093586


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 = 9.90;
constexpr double TEMP_START = 2.00;
constexpr double TEMP_END   = 0.01;
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) {
            double cur_temp = TEMP_START - TEMP_DIFF * timer.get_time();
            annealing1(cur_temp * cur_temp);
            annealing2(cur_temp * cur_temp);
            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 161488
Code Size 8186 Byte
Status AC
Exec Time 9925 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 1700 / 1000000 9547 / 1000000 14673 / 1000000 6596 / 1000000 1263 / 1000000 10718 / 1000000 9843 / 1000000 6263 / 1000000 7016 / 1000000 7510 / 1000000 4807 / 1000000 129 / 1000000 2170 / 1000000 4566 / 1000000 8867 / 1000000 1823 / 1000000 3921 / 1000000 4218 / 1000000 5043 / 1000000 2080 / 1000000 4608 / 1000000 3923 / 1000000 6620 / 1000000 2491 / 1000000 3931 / 1000000 1901 / 1000000 15671 / 1000000 9433 / 1000000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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 9925 ms 384 KB
00_sample_01 AC 9925 ms 1280 KB
10_random_00 AC 9925 ms 1408 KB
10_random_01 AC 9925 ms 1536 KB
10_random_02 AC 9925 ms 12928 KB
10_random_03 AC 9925 ms 4480 KB
10_random_04 AC 9925 ms 768 KB
10_random_05 AC 9925 ms 6656 KB
10_random_06 AC 9925 ms 4608 KB
10_random_07 AC 9925 ms 10624 KB
10_random_08 AC 9925 ms 2176 KB
20_full_00 AC 9925 ms 2304 KB
20_full_01 AC 9925 ms 4480 KB
20_full_02 AC 9925 ms 384 KB
20_full_03 AC 9925 ms 4352 KB
20_full_04 AC 9925 ms 1024 KB
20_full_05 AC 9925 ms 1536 KB
20_full_06 AC 9925 ms 6528 KB
20_full_07 AC 9925 ms 1664 KB
20_full_08 AC 9925 ms 896 KB
30_sparse_00 AC 9925 ms 6656 KB
30_sparse_01 AC 9925 ms 1408 KB
30_sparse_02 AC 9925 ms 6656 KB
30_sparse_03 AC 9925 ms 6656 KB
30_sparse_04 AC 9925 ms 2432 KB
30_sparse_05 AC 9925 ms 6528 KB
30_sparse_06 AC 9925 ms 12800 KB
30_sparse_07 AC 9925 ms 4480 KB
60_random_max_00 AC 9925 ms 12928 KB
70_full_max_00 AC 9925 ms 6528 KB