Submission #20853336

Source Code Expand

/** author: samari06,  created: 12.03.2021 16:01:55 **/
#include <bits/stdc++.h>
#define REP(i, N) for(int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
typedef vector<int> V;
typedef vector<ll> Vll;

#define XMAX 10000
#define XMIN 0
#define YMAX 10000
#define YMIN 0

typedef struct {
    int x,y,r;       //x,y,r
} input_t;
typedef struct {
    int a,b,c,d;     //a,b,c,d
} sol_t;
typedef vector<input_t> Vin;
typedef vector<sol_t> Vsol;

class Timer {
    private:
        clock_t time_start;    // 計測開始時間

    public:
        Timer() { restart(); }

        void restart() {
            time_start = clock();
        }

        clock_t elapsed() {             // 計測開始時間からの秒数を返す
            clock_t time_end = clock();
            return (time_end - time_start);
        }
};

// 疑似乱数列生成 (https://ja.wikipedia.org/wiki/Xorshift)
uint32_t xor32(void) {
  static uint32_t y = 2463534242;
  y ^= (y << 13); y ^= (y >> 17);  y ^= (y << 5);
  return y;
}

// 0以上1未満の小数をとる乱数
double rand01() {
    return (xor32()+0.5)*(1.0/UINT_MAX);
}


bool isin(const input_t &in, const sol_t &sol){
    return (sol.a <= in.x && sol.c > in.x && sol.b <= in.y && sol.d > in.y) && (sol.a >= XMIN && sol.c <= XMAX && sol.b >= YMIN && sol.d <= YMAX);
}

bool overlap(const sol_t &sol1, const sol_t &sol2){
    return !(sol1.d <= sol2.b || sol1.b >= sol2.d || sol1.c <= sol2.a || sol1.a >= sol2.c);
}

int score(const Vin &in, const Vsol &sol, const int n){
    double allp = 0.0;
    REP(i,n){
        //if(isin(in[i],sol[i])){
            double _s = (double)(sol[i].c-sol[i].a)*(sol[i].d-sol[i].b);
            double _r = (double)in[i].r;
            double p = (1.0-(1.0-(min(_r,_s)/max(_r,_s)))*(1.0-(min(_r,_s)/max(_r,_s))));
            
            allp += p;
            //printf("p:%lf, _s:%lf, _s:%lf\n", p, _s, _r);
        //}
    }
    return (int)round(1e9/n*allp);
}


bool update(const Vin &input, Vsol &sol , const int n, int tp, const int id, const int d){
    // rand01() > exp(cnt/1e7))
    if(((tp&1) == 0) && (sol[id].c-sol[id].a)*(sol[id].d-sol[id].b) < input[id].r) tp++;
    else if(((tp&1) == 1) && (sol[id].c-sol[id].a)*(sol[id].d-sol[id].b) >= input[id].r) tp--;
    if(tp <= 3){
        if(tp <= 1){
            if(tp&1) {
                sol[id].a-=d;
                if(!isin(input[id], sol[id])) return false;
                REP(i,n){
                    if(i == id) continue;
                    if(!overlap(sol[i], sol[id])) continue;
                    sol[i].c-=d;
                    if(!isin(input[i], sol[i])) return false;
                }
            } else {
                sol[id].a++;
                return isin(input[id], sol[id]);
            }
        } else {
            if(tp&1) {
                sol[id].b-=d;
                if(!isin(input[id], sol[id])) return false;
                REP(i,n){
                    if(i == id) continue;
                    if(!overlap(sol[i], sol[id])) continue;
                    sol[i].d-=d;
                    if(!isin(input[i], sol[i])) return false;
                }
            } else {
                sol[id].b++;
                return isin(input[id], sol[id]);
            }
        }
    } else {
        if(tp <= 5){
            if(tp&1) {
                sol[id].c+=d;
                if(!isin(input[id], sol[id])) return false;
                REP(i,n){
                    if(i == id) continue;
                    if(!overlap(sol[i], sol[id])) continue;
                    sol[i].a+=d;
                    if(!isin(input[i], sol[i])) return false;
                }
            } else {
                sol[id].c--;
                return isin(input[id], sol[id]);
            }
        } else {
            if(tp&1) {
                sol[id].d+=d;
                if(!isin(input[id], sol[id])) return false;
                REP(i,n){
                    if(i == id) continue;
                    if(!overlap(sol[i], sol[id])) continue;
                    sol[i].b+=d;
                    if(!isin(input[i], sol[i])) return false;
                }
            } else {
                sol[id].d--;
                return isin(input[id], sol[id]);
            }
        }
    }

    return true;
}

Vsol solve(Vin &input, const int n){
    Timer tmr;
    const double T0 = 5000;
    const double T1 = 100;
    const double TL = 1.9;

    double T = T0;

    //初期解の生成
    Vsol sol(n);
    REP(i,n) {
        sol[i].a = input[i].x; sol[i].b = input[i].y;
        sol[i].c = input[i].x+1; sol[i].d = input[i].y+1;
    }

    int scr = score(input, sol, n);
    Vsol bestsol(n); bestsol = sol;
    int bestscr = scr;

    int cnt = 0, lup = 0;
    double time = (double)tmr.elapsed() / CLOCKS_PER_SEC;

    Vsol psol = sol;
    int pscr = scr;
    bool valid;
    int id, tp;
    //double prob = exp(time / TL);

    while (time < TL) {
        id = xor32() % n;
        tp = xor32() % 8;
        
        psol = sol;
        pscr = scr;
        valid = update(input, sol, n, tp, id, (int)(20*(T-T1)/(T0-T1)) + 1);  // 解の有効性
        //if(T < TL*0.1) break;

        //int dscr = score(input, sol, n) - pscr;

        if(valid){
            scr = score(input, sol, n);
            //const double prob = exp(time / TL);     // 負の変形の採択率

            if(scr < pscr && (rand01()*(T0-T1) + T1 > T)){
                sol = psol;
                scr = pscr;
            }
        }else{
            sol = psol;
        }

        if(scr > bestscr) bestsol = sol;
        cnt++;
        if(cnt % 1000 == 0) {
            time = (double)tmr.elapsed() / CLOCKS_PER_SEC;
            const double progress = time/TL;
            T = pow(T0, 1.0-progress) * pow(T1, progress);
        }
    }

    //更新回数と反復回数
    //printf("count: %d / %d\n", lup, cnt);

    return bestsol;
}

int main(){
    //入力
    int n;
    scanf("%d", &n);
    Vin input(n);
    REP(i,n) scanf("%d%d%d", &(input[i].x), &(input[i].y), &(input[i].r));
    
    //求解
    Vsol sol = solve(input, n);

    //出力
    REP(i,n) {
        printf("%d %d %d %d\n",sol[i].a,sol[i].b,sol[i].c,sol[i].d);
    }

    //score
    //printf("score: %d\n",score(input,sol,n));

    //充填率
    /*
    int half = 0;
    REP(i,n){
        printf("%3d : %lf\n", i, (double)(sol[i].c-sol[i].a)*(sol[i].d-sol[i].b) / input[i].r);
        if((double)(sol[i].c-sol[i].a)*(sol[i].d-sol[i].b) / input[i].r < 0.8) half++;
    }
    printf("half :%d", half);
    */

    return 0;
}

Submission Info

Submission Time
Task A - AtCoder Ad
User samari06
Language C++ (GCC 9.2.1)
Score 48105928551
Code Size 6812 Byte
Status AC
Exec Time 1916 ms
Memory 4212 KiB

Compile Error

./Main.cpp: In function ‘Vsol solve(Vin&, int)’:
./Main.cpp:165:18: warning: unused variable ‘lup’ [-Wunused-variable]
  165 |     int cnt = 0, lup = 0;
      |                  ^~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:215:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  215 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
./Main.cpp:217:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  217 |     REP(i,n) scanf("%d%d%d", &(input[i].x), &(input[i].y), &(input[i].r));
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name test_ALL
Score / Max Score 48105928551 / 50000000000
Status
AC × 50
Set Name Test Cases
test_ALL test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt
Case Name Status Exec Time Memory
test_0000.txt AC 1915 ms 4208 KiB
test_0001.txt AC 1908 ms 3968 KiB
test_0002.txt AC 1912 ms 3860 KiB
test_0003.txt AC 1909 ms 4108 KiB
test_0004.txt AC 1908 ms 4028 KiB
test_0005.txt AC 1912 ms 4204 KiB
test_0006.txt AC 1908 ms 4120 KiB
test_0007.txt AC 1912 ms 3968 KiB
test_0008.txt AC 1904 ms 4212 KiB
test_0009.txt AC 1910 ms 3860 KiB
test_0010.txt AC 1910 ms 4192 KiB
test_0011.txt AC 1912 ms 3968 KiB
test_0012.txt AC 1912 ms 3944 KiB
test_0013.txt AC 1912 ms 4144 KiB
test_0014.txt AC 1912 ms 4008 KiB
test_0015.txt AC 1912 ms 3940 KiB
test_0016.txt AC 1908 ms 4028 KiB
test_0017.txt AC 1908 ms 4196 KiB
test_0018.txt AC 1908 ms 4196 KiB
test_0019.txt AC 1912 ms 3944 KiB
test_0020.txt AC 1916 ms 4204 KiB
test_0021.txt AC 1908 ms 4212 KiB
test_0022.txt AC 1912 ms 4008 KiB
test_0023.txt AC 1908 ms 4024 KiB
test_0024.txt AC 1904 ms 4036 KiB
test_0025.txt AC 1916 ms 3972 KiB
test_0026.txt AC 1908 ms 4208 KiB
test_0027.txt AC 1908 ms 4076 KiB
test_0028.txt AC 1915 ms 4032 KiB
test_0029.txt AC 1911 ms 4116 KiB
test_0030.txt AC 1908 ms 4204 KiB
test_0031.txt AC 1912 ms 4076 KiB
test_0032.txt AC 1916 ms 4096 KiB
test_0033.txt AC 1911 ms 4192 KiB
test_0034.txt AC 1912 ms 3944 KiB
test_0035.txt AC 1908 ms 4024 KiB
test_0036.txt AC 1904 ms 4100 KiB
test_0037.txt AC 1908 ms 4024 KiB
test_0038.txt AC 1904 ms 4112 KiB
test_0039.txt AC 1912 ms 4196 KiB
test_0040.txt AC 1911 ms 4204 KiB
test_0041.txt AC 1908 ms 4120 KiB
test_0042.txt AC 1912 ms 4076 KiB
test_0043.txt AC 1908 ms 3916 KiB
test_0044.txt AC 1910 ms 4104 KiB
test_0045.txt AC 1916 ms 4192 KiB
test_0046.txt AC 1908 ms 3920 KiB
test_0047.txt AC 1904 ms 4208 KiB
test_0048.txt AC 1912 ms 3968 KiB
test_0049.txt AC 1908 ms 4080 KiB