結果
| 問題 | No.5016 Worst Mayor |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-05-08 15:42:09 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,866 ms / 2,000 ms |
| コード長 | 14,162 bytes |
| 記録 | |
| コンパイル時間 | 7,295 ms |
| コンパイル使用メモリ | 391,920 KB |
| 実行使用メモリ | 30,076 KB |
| スコア | 23,640,363,348 |
| 平均クエリ数 | 400.00 |
| 最終ジャッジ日時 | 2026-05-08 15:43:55 |
| 合計ジャッジ時間 | 105,332 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma GCC target("prefer-vector-width=512")
#pragma GCC target("avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,avx512vbmi,avx512vbmi2,avx512vnni,avx512bitalg,avx512vpopcntdq")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T &a,T b){
if(a<b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmin_ref(T &a,const T &b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace Timer{
chrono::steady_clock::time_point program_start,start;
void program_start_snap(){
program_start=start=chrono::steady_clock::now();
}
void snap(){
start=chrono::steady_clock::now();
}
int get_ms(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
return ms;
}
int get_ms_all_program(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
return ms;
}
}
mt19937 mt;
uint32_t rand_int(uint32_t r){ //[0,r)
assert(r!=0);
return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){ //[l,r)
assert(l<r);
return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){ //[0.0,1.0]
return mt()*one_div_mt_max;
}
double rand_double(double l,double r){ //[l,r]
return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
assert(!v.empty());
return v[rand_int(len(v))];
}
template<class T> void add(vector<T> &a,vector<T> b){
for(auto i:b) a.push_back(i);
}
constexpr int N=14,K=3000,T=400,M=1000000;
array<int,K> A,B;
array<array<int,4>,N*N> G;
vector<pii> E;
int one(int i,int j){
return i*N+j;
}
pii two(int x){
return {x/N,x%N};
}
namespace Solver{
array<array<int,N*N>,N*N> start_dist;
array<int,N*4*1000> dist_cnt;
vector<pii> first_edges;
struct State{
vector<pii> edges;
int score=0;
State(){
edges=first_edges;
score=get_score();
}
int get_score(){
int sz=len(edges);
vector<int> income;
income.push_back(0);
auto dist=start_dist;
for(auto [u,v]:edges){
rep(i,N*N){
rep(j,N*N){
chmin(dist[i][j],dist[i][u]+223+dist[v][j]);
chmin(dist[i][j],dist[i][v]+223+dist[u][j]);
}
}
int sum=0;
rep(i,K){
sum+=dist_cnt[dist[A[i]][B[i]]];
}
income.push_back(sum*60);
}
const int P=100;
vector<vector<pii>> dp(sz+1,vector<pii>(P,{T+1,T+1}));
dp[0][1]={0,-M};
rep(k,sz){
rep(i,P){
auto [turn,money]=dp[k][i];
if(turn==T+1) continue;
money=-money;
replr(j,i,P){
int cost=floor((double)1e7/sqrt(j));
int add_turn=j-i;
int income_income=(50000+income[k]);
int income_turn=(max(0,cost-(money+income[k]*add_turn))+income_income-1)/income_income;
int new_turn=turn+add_turn+income_turn+1;
//if(dp[k+1][j].first<new_turn) continue;
int new_money=money;
new_money+=income[k]*add_turn;
new_money+=income_income*income_turn;
new_money-=(int)floor((double)1e7/sqrt(j));
assert(0<=new_money);
new_money+=income[k+1];
chmin(dp[k+1][j],{new_turn,-new_money});
}
}
}
int best_money=0;
vector<tii> ans;
rep(k,sz+1){
rep(i,P){
auto [turn,money]=dp[k][i];
if(T<turn) continue;
money=-money;
money+=(T-turn)*(50000+income[k]);
chmax(best_money,money);
}
}
return best_money;
}
void output_ans(){
int sz=len(edges);
vector<int> income;
income.push_back(0);
auto dist=start_dist;
for(auto [u,v]:edges){
rep(i,N*N){
rep(j,N*N){
chmin(dist[i][j],dist[i][u]+223+dist[v][j]);
chmin(dist[i][j],dist[i][v]+223+dist[u][j]);
}
}
int sum=0;
rep(i,K){
sum+=dist_cnt[dist[A[i]][B[i]]];
}
income.push_back(sum*60);
}
const int P=100;
vector<vector<pii>> dp(sz+1,vector<pii>(P,{T+1,T+1}));
vector<vector<qii>> pre(sz+1,vector<qii>(P,{-1,-1,-1,-1}));
dp[0][1]={0,-M};
rep(k,sz){
rep(i,P){
auto [turn,money]=dp[k][i];
if(turn==T+1) continue;
money=-money;
replr(j,i,P){
int cost=floor((double)1e7/sqrt(j));
int add_turn=j-i;
int income_income=(50000+income[k]);
int income_turn=(max(0,cost-(money+income[k]*add_turn))+income_income-1)/income_income;
int new_turn=turn+add_turn+income_turn+1;
//if(dp[k+1][j].first<new_turn) continue;
int new_money=money;
new_money+=income[k]*add_turn;
new_money+=income_income*income_turn;
new_money-=(int)floor((double)1e7/sqrt(j));
assert(0<=new_money);
new_money+=income[k+1];
if(chmin(dp[k+1][j],{new_turn,-new_money})) pre[k+1][j]={k,i,add_turn,income_turn};
}
}
}
int best_money=0,nk=-1,ni=-1,last_push=0;
vector<tii> ans;
rep(k,sz+1){
rep(i,P){
auto [turn,money]=dp[k][i];
if(T<turn) continue;
money=-money;
money+=(T-turn)*(50000+income[k]);
if(chmax(best_money,money)){
nk=k;
ni=i;
ans.clear();
last_push=T-turn;
}
}
}
rep(_,last_push) ans.emplace_back(3,-1,-1);
cerr << best_money << endl;
while(0<=nk){
auto [pk,pi,add_turn,income_turn]=pre[nk][ni];
if(pk==-1) break;
ans.emplace_back(1,edges[pk].first,edges[pk].second);
rep(_,income_turn) ans.emplace_back(3,-1,-1);
rep(_,add_turn) ans.emplace_back(2,-1,-1);
nk=pk;
ni=pi;
}
reverse(all(ans));
assert(len(ans)==T);
for(auto [t,u,v]:ans){
int x,y;
cin >> x >> y;
if(t==1){
auto [a,b]=two(u);
auto [c,d]=two(v);
cout << "1 " << a+1 << ' ' << b+1 << ' ' << c+1 << ' ' << d+1 << '\n';
cout.flush();
}else{
cout << t << '\n';
cout.flush();
}
}
}
};
void init(){
rep(i,N*N){
start_dist[i].fill(INF);
priority_queue<pii,vector<pii>,greater<pii>> pq;
start_dist[i][i]=0;
pq.push({0,i});
while(!pq.empty()){
auto [d,x]=pq.top();
pq.pop();
if(start_dist[i][x]!=d) continue;
for(auto y:G[x]){
if(y==-1) continue;
if(chmin(start_dist[i][y],start_dist[i][x]+1000)){
pq.push({start_dist[i][y],y});
}
}
}
}
dist_cnt.fill(-1);
rep(i,N*2){
for(int j=0;j*223<=N*2*1000;j++){
assert(dist_cnt[i*1000+j*223]==-1);
dist_cnt[i*1000+j*223]=j;
}
}
}
void calc_edges(){
auto dist=start_dist;
int pre_sum=0;
set<pii> st;
array<bool,N*N> in;
in.fill(false);
first_edges.clear();
rep(loop,100){
if(1800<Timer::get_ms()) return;
int best_sum=-1;
int best_u=-1,best_v=-1;
for(auto [u,v]:E){
if(st.contains({u,v})) continue;
if(0<loop&&(!in[u]&&!in[v])) continue;
auto now_dist=dist;
rep(i,N*N){
rep(j,N*N){
chmin(now_dist[i][j],now_dist[i][u]+223+now_dist[v][j]);
chmin(now_dist[i][j],now_dist[i][v]+223+now_dist[u][j]);
}
}
int sum=rand_int(200);
rep(i,K){
sum+=dist_cnt[now_dist[A[i]][B[i]]];
}
if(chmax(best_sum,sum)){
best_u=u;
best_v=v;
}
}
if(pre_sum==best_sum) break;
pre_sum=best_sum;
int u=best_u,v=best_v;
rep(i,N*N){
rep(j,N*N){
chmin(dist[i][j],dist[i][u]+223+dist[v][j]);
chmin(dist[i][j],dist[i][v]+223+dist[u][j]);
}
}
first_edges.emplace_back(u,v);
st.insert({u,v});
in[u]=true;
in[v]=true;
}
}
void solve(){
init();
int best_score=0;
State best_state;
while(Timer::get_ms()<1800){
calc_edges();
State state;
if(best_score<state.score) best_state=state;
}
best_state.output_ans();
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Timer::program_start_snap();
int k,t;
cin >> k >> t;
assert(k==K);
assert(t==T);
A.fill(-1);
B.fill(-1);
rep(i,K){
int a,b,c,d;
cin >> a >> b >> c >> d;
a--;
b--;
c--;
d--;
A[i]=one(a,b);
B[i]=one(c,d);
}
rep(i,N*N) G[i].fill(-1);
rep(i,N){
rep(j,N){
if(j+1<N){
G[one(i,j)][3]=one(i,j+1);
G[one(i,j+1)][2]=one(i,j);
E.emplace_back(one(i,j),one(i,j+1));
}
if(i+1<N){
G[one(i,j)][1]=one(i+1,j);
G[one(i+1,j)][0]=one(i,j);
E.emplace_back(one(i,j),one(i+1,j));
}
}
}
Solver::solve();
exit(0);
}