Submission #2127172

---

Source Code Expand

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>=0;i--)
//#define I(n) scanf("%d", &(n))
#define I(n) FastIO::scan((n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#include <bits/stdc++.h>
using namespace std;
 
//------------------------------typedef集
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
 
#undef getchar_unlocked
inline unsigned long long rdtsc()
{
#ifdef __amd64
  unsigned long long a, d;
  __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
  return (d << 32) | a;
#else
  unsigned long long x;
  __asm__ volatile ("rdtsc" : "=A" (x));
  return x;
#endif
}
 
inline double gettime(){return rdtsc()/2793344000.0;}
inline double elapsed(double st){return gettime()-st;}
 
struct FastIO{
    template <class Integral>
    static void scan(Integral &x) {
        int k, m = 0;
        x = 0;
        for (;;) {
            k = getchar_unlocked();
            if (k == '-') {
                m = 1;
                break;
            } else if ('0' <= k && k <= '9') {
                x = k-'0';
                break;
            }
        }
        for (;;) {
            k = getchar_unlocked();
            if (k < '0' || k > '9')
                break;
            x = (x << 3) + (x << 1) + k-'0';
        }
        if (m)
            x = -x;
    }
};
 
int E; //input
int V,u,v,vemb;
unsigned char w,g[512][512];
 
unsigned int x01,x02,y01,y02;
int ippen,intx,inty,cntr,delta[4],ret,exchtmp,score,dscore,bestscore;
unsigned short gemb[64][64],bestgemb[64][64];
bool scattered[512];
vi top8;
vector<pi> vscore;
double stt;
float temper,prob,targetno;
 
uint32_t xor128() { //128とは言ってない
  static uint64_t x = 88172645463325252ULL;
  x ^= (x << 13); x ^= (x >> 7);
  return x ^= (x << 17);
}
 
 
/*inline int lkup(int x, int y){
    int t = gemb[x][y];
    return *(tgtg+t);
}*/
 
inline unsigned char adjc(int x, int y, int tgt){
 
    return tgt ?
 
    //unsigned char r = 0;
    //FOR(ix,-1,2) FOR(iy,-1,2) r += lkup(x+ix,y+iy);
    /*
    FOR(ix,-1,2) {FOR(iy,-1,2) {
        r += ix || iy ? g[tgt][gemb[x+ix][y+iy]] : 0;
    } }
    */
 
     g[tgt][gemb[x-1][y-1]]
     + g[tgt][gemb[x-1][y]]
     + g[tgt][gemb[x-1][y+1]]
     + g[tgt][gemb[x][y-1]]
     + g[tgt][gemb[x][y+1]]
     + g[tgt][gemb[x+1][y-1]]
     + g[tgt][gemb[x+1][y]]
     + g[tgt][gemb[x+1][y+1]]
 
 
    : 0;
}
inline unsigned char jisuu(int x, int y){
    return
 
    (gemb[x-1][y-1] != 0) + (gemb[x-1][y] != 0) + (gemb[x-1][y+1] != 0) +
    (gemb[x][y-1] != 0) + (gemb[x][y+1] != 0) +
    (gemb[x+1][y-1] != 0 ) + (gemb[x+1][y] != 0) + (gemb[x+1][y+1] != 0);
 
}
inline int allscore(){
    int r = 0;
    FOR(i,1,ippen+1){ FOR(j,1,ippen+1){
        r += adjc(i,j,gemb[i][j]);
    } }
    return r;
}
// int exchr;
inline int exch_remote_nocheck(int xa, int ya, int xb, int yb, int dept, int dest){
    int exchr = (adjc(xa,ya,dest) + adjc(xb,yb,dept) - adjc(xa,ya,dept) - adjc(xb,yb,dest));
    exchr += abs(xa-xb) <= 1 && abs(ya-yb) <= 1 ? g[dept][dest]*2 : 0;
    return exchr;
}
 
int main(){
    stt = gettime();
 
    I(V); I(E);
    REP(i,V+1){
        vscore.pb(mp(0,i));
    }
    REP(i,E){
        I(u); I(v); I(w);
        g[u][v] = g[v][u] = w;
        vscore[u].first += w;
        vscore[v].first += w;
    }
 
    FOR(i,1,V+1){
        top8.clear();
        FOR(j,1,V+1) top8.pb(g[i][j]);
        sort(top8.begin(),top8.end(),greater<int>());
        REP(j,min(V,8)) score += top8[j];
    }
    vscore.erase(vscore.begin());
    sort(vscore.begin(),vscore.end(),greater<pi>());
    const float startTemp = (double)score/V/39;
 
    I(vemb);
    ippen = sqrt(vemb);
    intx = inty = ippen/2;
 
    cntr = 0;
    int move = 0;
 
    scattered[0] = 1;
    int sctmp = 0;
    int scidx = 0;
    int vsq = (sqrt((double)V)/sqrt(3.1415926536))+1;
    vsq = ippen;
    //if ((V-4)/(double)vemb < 0.75) vsq = ippen;
    //if ( vemb - 2 * ippen <= V ) vsq++;
    while (cntr != V){
        move++;
        REP(i,move){
            if ( (intx-(ippen/2)) * (intx-(ippen/2)) + (inty-(ippen/2)) * (inty-(ippen/2)) <= vsq * vsq ){
                if (0 >= intx || intx > ippen || 0 >= inty || inty > ippen) { vsq++; intx++; continue; }
                if (cntr==0) {
                    gemb[intx][inty] = vscore[cntr].second;
                    scattered[vscore[cntr].second] = 1;
                } else {
                    sctmp = scidx = 0;
                    REP(j,V+1){
                        if (scattered[j]) continue;
                        exchtmp = adjc(intx,inty,j);
                        if (sctmp <= exchtmp){
                            sctmp = exchtmp;
                            scidx = j;
                        }
                    }
                    gemb[intx][inty] = scidx;
                    scattered[scidx] = 1;
                }
                cntr++;
                if (cntr == V) break;
            }
            intx++;
        }
        if (cntr == V) break;
        REP(i,move){
            if ( (intx-(ippen/2)) * (intx-(ippen/2)) + (inty-(ippen/2)) * (inty-(ippen/2)) <= vsq * vsq ){
                if (0 >= intx || intx > ippen || 0 >= inty || inty > ippen) { vsq++; inty++; continue; }
                sctmp = scidx = 0;
                REP(j,V+1){
                    if (scattered[j]) continue;
                    exchtmp = adjc(intx,inty,j);
                    if (sctmp <= exchtmp){
                        sctmp = exchtmp;
                        scidx = j;
                    }
                }
                gemb[intx][inty] = scidx;
                scattered[scidx] = 1;
                cntr++;
                if (cntr == V) break;
            }
            inty++;
        }
        if (cntr == V) break;
        move++;
        REP(i,move){
            if ( (intx-(ippen/2)) * (intx-(ippen/2)) + (inty-(ippen/2)) * (inty-(ippen/2)) <= vsq * vsq ){
                if (0 >= intx || intx > ippen || 0 >= inty || inty > ippen) { vsq++; intx--; continue; }
                sctmp = scidx = 0;
                REP(j,V+1){
                    if (scattered[j]) continue;
                    exchtmp = adjc(intx,inty,j);
                    if (sctmp <= exchtmp){
                        sctmp = exchtmp;
                        scidx = j;
                    }
                }
                gemb[intx][inty] = scidx;
                scattered[scidx] = 1;
                cntr++;
                if (cntr == V) break;
            }
            intx--;
        }
        if (cntr == V) break;
        REP(i,move){
            if ( (intx-(ippen/2)) * (intx-(ippen/2)) + (inty-(ippen/2)) * (inty-(ippen/2)) <= vsq * vsq ){
                if (0 >= intx || intx > ippen || 0 >= inty || inty > ippen) { vsq++; inty--; continue; }
                sctmp = scidx = 0;
                REP(j,V+1){
                    if (scattered[j]) continue;
                    exchtmp = adjc(intx,inty,j);
                    if (sctmp <= exchtmp){
                        sctmp = exchtmp;
                        scidx = j;
                    }
                }
                gemb[intx][inty] = scidx;
                scattered[scidx] = 1;
                cntr++;
                if (cntr == V) break;
            }
            inty--;
        }
        if (cntr == V) break;
    }
    cout << "";
    //cerr << elapsed(stt) << endl;
    vsq = (sqrt(V)/sqrt(3.1415926535))+1;
    score = allscore()/2;
    //REP(i,ippen) {REP(j,ippen){ fprintf(stderr,"%3d",gemb[i][j]);} cerr << endl; }
    //cerr << score << endl;
 
    const float endTemp = 0.8;
    double t = elapsed(stt);
    const double limittime = 9.997;
    const unsigned int denom = 1 << 30;
    const int sz = sizeof(gemb);
    memcpy(bestgemb,gemb,sz);
    bestscore = score;
    //int bt = 1;
    //int lp = 0;
    while(t < limittime){
        temper = startTemp + (endTemp - startTemp) * t * t / limittime / limittime;
        /*
        lp++;
        if (bt < t*10){
            cerr <<score << " " << bestscore << " " << bt << " " << temper << endl;
            bt++;
        }
        */
        REP(gg,1000){
            x01 = xor128()%ippen+1;
            y01 = xor128()%ippen+1;
            x02 = xor128()%ippen+1;
            y02 = xor128()%ippen+1;
            u = gemb[x01][y01];
            v = gemb[x02][y02];
            if (!(u | v)) continue;
 
            dscore = jisuu(x01,y01) - jisuu(x02,y02);
            targetno = v ? dscore : 0;
            targetno -= u ? dscore : 0;
            targetno *= (limittime - t)/limittime/2;
            dscore = exch_remote_nocheck(x01,y01,x02,y02,u,v);
 
            prob = expf((dscore+targetno)/temper);
 
            if (prob * denom > (float)(xor128() % denom)){
                score += dscore;
                swap(gemb[x01][y01],gemb[x02][y02]);
            }
            if(score > bestscore){
                bestscore = score;
                memcpy(bestgemb,gemb,sz);
            }
        }
        t = elapsed(stt);
    }
    //cerr << t << endl;
    //REP(i,ippen) {REP(j,ippen){ fprintf(stderr,"%3d",gemb[i][j]);} cerr << endl; }
    FOR(x,1,ippen+1){ FOR(y,1,ippen+1){
        if (bestgemb[x][y]){
            printf("%d %d\n",bestgemb[x][y],(x-1)*ippen+y);
        }
    } }
    //cerr << lp << endl;
}

Submission Info

Judge Result