結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 Kahuka
|
| 提出日時 | 2023-04-29 18:58:11 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,131 bytes |
| コンパイル時間 | 2,672 ms |
| コンパイル使用メモリ | 212,496 KB |
| 実行使用メモリ | 24,420 KB |
| スコア | 13,144,154,516 |
| 平均クエリ数 | 392.00 |
| 最終ジャッジ日時 | 2023-04-29 18:59:56 |
| 合計ジャッジ時間 | 40,187 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 49 TLE * 1 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0; i<n; i++)#define reps(i,s,n) for(int i=s; i<n; i++)#define per(i,n) for(int i=n-1; i>=0; i--)#define pers(i,n,s) for(int i=n-1; i>=s; i--)#define all(v) v.begin(),v.end()#define fi first#define se second#define pb push_back#define si(v) int(v.size())#define lb(v,n) lower_bound(all(v),n)#define lbi(v,n) int(lower_bound(all(v),n) - v.begin())#define ub(v,n) upper_bound(all(v),n)#define ubi(v,n) int(upper_bound(all(v),n) - v.begin())#define mod 1000000007#define infi 1010000000#define infl 1100000000000000000#define outve(v) {for(auto i : v) cout << i << " ";cout << endl;}#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}#define IN(n,m,v) rep(i,n) rep(j,m){cin >> v[i][j];}#define cyes cout << "Yes" << endl#define cno cout << "No" << endl#define cYES cout << "YES" << endl#define cNO cout << "NO" << endl#define csp << " " <<#define outset(n) cout << fixed << setprecision(n);using namespace std;using ll = long long;using ull = unsigned long long;using uint = unsigned int;using ld = long double;using vi = vector<int>;using vvi = vector<vector<int>>;using vd = vector<double>;using vvd = vector<vector<double>>;using vl = vector<ll>;using vvl = vector<vector<ll>>;using vs = vector<string>;using pii = pair<int,int>;using pll = pair<ll,ll>;template<typename T> using ve = vector<T>;template<typename T> using vv = vector<vector<T>>;template<typename T> using pq2 = priority_queue<T>;template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}int popcnt(uint n) {return __builtin_popcount(n);}int popcntl(ull n) {return __builtin_popcountll(n);}int bsr(uint n) {return 31 - __builtin_clz(n);}int bsrl(ull n) {return 63 - __builtin_clzll(n);}int bsf(uint n) {return __builtin_ctz(n);}int bsfl(ull n) {return __builtin_ctzll(n);}unsigned int xorshift() {static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123;unsigned int tt = (tx^(tx<<11));tx = ty; ty = tz; tz = tw;return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) );}double TIME_LIMIT = 1.80;int LOCAL = 0;int TEATER = 0;constexpr int dh[4] = {-1,0,1,0};constexpr int dw[4] = {0,-1,0,1};constexpr int N = 14;constexpr int M = 3000;constexpr int T = 400;int home[M];int company[M];ll money,people;vvi road;void solve(){int ti = clock();double time = 1.0 * (clock() - ti) / CLOCKS_PER_SEC;int m,t;cin >> m >> t;int road[N][N];rep(i,N) rep(j,N) road[i][j] = 0;int road_num = 0;rep(i,m) {int a,b,c,d;cin >> a >> b >> c >> d;a--,b--,c--,d--;home[i] = a*N+b;company[i] = c*N+d;}int build_road = 1;ll road_incom = 0;ll next_road_incom = -1;int next_hwk = -1;{ll score_max = -infl;int hwk = -1;rep(a,N) rep(b,N) rep(k,4) if(k == 2 || k == 3){road[a][b] |= 1<<k;road[a+dh[k]][b+dw[k]] |= 1<<((k+2)%4);if(!(a == 7 && b == 7 && k == 2)) {road[a][b] &= ~(1<<k);road[a+dh[k]][b+dw[k]] &= ~(1<<((k+2)%4));continue;}ll D[196][196];int cn[196][196];rep(i,N) rep(j,N){int s = i*N+j;rep(h,N) rep(w,N) D[s][h*N+w] = infi;rep(h,N) rep(w,N) cn[s][h*N+w] = 0;pq1<ll> pq;pq.push(0*10000+i*100+j);while (!pq.empty()) {ll chw = pq.top();pq.pop();ll c = chw/10000;int h = (chw%10000)/100, w = chw%100;if(D[s][h*N+w] < c) continue;rep(k,4) {int nh = h + dh[k], nw = w + dw[k];if(nh < 0 || nh >= N || nw < 0 || nw >= N) continue;if(chmin(D[s][nh*N+nw], c+(road[h][w]&1<<k ? 223 : 10000))) {pq.push(D[s][nh*N+nw]*10000ll + nh*100 + nw);cn[s][nh*N+nw] = cn[s][h*N+w]+(road[h][w]&1<<k ? 1 : 0);}}}}ll c = 0;rep(i,M) c += 60ll*cn[home[i]][company[i]];if(chmax(score_max,c)) hwk = a*1000 + b*10 + k;road[a][b] &= ~(1<<k);road[a+dh[k]][b+dw[k]] &= ~(1<<((k+2)%4));}next_hwk = hwk;next_road_incom = score_max;}money = 1000000, people = 1;rep(t,T){if(LOCAL == 0) cin >> money >> people;if(money == -1) return;if(build_road==1 && people > 0 && money > ll(10000000.0/sqrt((double)people))){if(road_num < 100 && next_hwk >= 0){int x = next_hwk/1000, y = (next_hwk%1000)/10, k = next_hwk%10;int z = x + dh[k], w = y+dw[k];cout << 1 csp x+1 csp y+1 csp z+1 csp w+1 << endl;if(LOCAL) money -= ll(10000000.0/sqrt((double)people));road[x][y] |= 1<<k;road[z][w] |= 1<<((k+2)%4);road_num++;road_incom += next_road_incom;ll score_max = -infl;int hwk = -1;rep(a,N) rep(b,N) {if(build_road == 0) break;int ff = 0;rep(kk,4){int nh = a + dh[kk], nw = b + dw[kk];if(nh < 0 || nh >= N || nw < 0 || nw >= N) continue;if(road[nh][nw] & 1 << kk) ff++;}if(ff == 0) continue;rep(k,4) if(k == 2 || k == 3) {int nh = a + dh[k], nw = b + dw[k];if(nh < 0 || nh >= N || nw < 0 || nw >= N) continue;if(road[a][b] & 1 << k) continue;time = 1.0 * (clock() - ti) / CLOCKS_PER_SEC;if(time > TIME_LIMIT) {build_road = 0;break;}if(hwk != -1) {if(xorshift()%20 != 0) continue;}road[a][b] |= 1<<k;road[a+dh[k]][b+dw[k]] |= 1<<((k+2)%4);ll D[196][196];int cn[196][196];rep(i,N) rep(j,N){int s = i*N+j;rep(h,N) rep(w,N) D[s][h*N+w] = infi;rep(h,N) rep(w,N) cn[s][h*N+w] = 0;pq1<ll> pq;pq.push(0*10000+i*100+j);while (!pq.empty()) {ll chw = pq.top();pq.pop();ll c = chw/10000;int h = (chw%10000)/100, w = chw%100;if(D[s][h*N+w] < c) continue;rep(k,4) {int nh = h + dh[k], nw = w + dw[k];if(nh < 0 || nh >= N || nw < 0 || nw >= N) continue;if(chmin(D[s][nh*N+nw], c+(road[h][w]&1<<k ? 223 : 10000))) {pq.push(D[s][nh*N+nw]*10000ll + nh*100 + nw);cn[s][nh*N+nw] = cn[s][h*N+w]+(road[h][w]&1<<k ? 1 : 0);}}}}ll c = 0;rep(i,M) c += 60ll*(ll)cn[home[i]][company[i]];if(chmax(score_max,c)) hwk = a*1000 + b*10 + k;road[a][b] &= ~(1<<k);road[a+dh[k]][b+dw[k]] &= ~(1<<((k+2)%4));}}next_hwk = hwk;next_road_incom = score_max;}else{build_road = 0;cout << 3 << endl;if(LOCAL) money += 50000;}}else{if(build_road == 1){if(people < 40){cout << 2 << endl;if(LOCAL) people++;}else{cout << 3 << endl;if(LOCAL) money += 50000;}}else {cout << 3 << endl;if(LOCAL) money += 50000;}}if(LOCAL){ll D[196][196];int cn[196][196];rep(i,N) rep(j,N){int s = i*N+j;rep(h,N) rep(w,N) D[s][h*N+w] = infi;rep(h,N) rep(w,N) cn[s][h*N+w] = 0;pq1<ll> pq;pq.push(0*10000+i*100+j);while (!pq.empty()) {ll chw = pq.top();pq.pop();ll c = chw/10000;int h = (chw%10000)/100, w = chw%100;if(D[s][h*N+w] < c) continue;rep(k,4) {int nh = h + dh[k], nw = w + dw[k];if(nh < 0 || nh >= N || nw < 0 || nw >= N) continue;if(chmin(D[s][nh*N+nw], c+(road[h][w]&1<<k ? 223 : 10000))) {pq.push(D[s][nh*N+nw]*10000ll + nh*100 + nw);cn[s][nh*N+nw] = cn[s][h*N+w]+(road[h][w]&1<<k ? 1 : 0);}}}}ll c = 0;rep(i,M) c += 60ll*cn[home[i]][company[i]];cerr << t csp money csp people csp c csp next_road_incom csp time << endl;money += c;}}rep(i,N) {rep(j,N) {int f = 0;rep(k,4) if(road[i][j] & 1 << k) f++;if(f > 0) cerr << "o ";else cerr << ". ";}cerr << endl;}time = 1.0 * (clock() - ti) / CLOCKS_PER_SEC;cerr << time csp road_num csp money << endl;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;}