結果
| 問題 | No.5016 Worst Mayor |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-05-08 10:50:43 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 236 ms / 2,000 ms |
| コード長 | 12,147 bytes |
| 記録 | |
| コンパイル時間 | 3,763 ms |
| コンパイル使用メモリ | 368,812 KB |
| 実行使用メモリ | 104,488 KB |
| スコア | 12,881,957,976 |
| 平均クエリ数 | 400.00 |
| 最終ジャッジ日時 | 2026-05-08 10:51:10 |
| 合計ジャッジ時間 | 18,014 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#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);
}
template<class SA_State,int limit_ms,double start_temp,double end_temp=0.0> SA_State SA(const SA_State &first_state){
SA_State state=first_state,best_state=state;
int loop_cnt=0,accept_cnt=0,update_cnt=0;
int ms=0;
double temp=start_temp;
Timer::snap();
while(true){
if(true){
ms=Timer::get_ms();
if(limit_ms<=ms) break;
//double t=(double)ms/limit_ms;
temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
//temp=pow(start_temp,1-t)*pow(end_temp,t);
}
loop_cnt++;
double accept_diff=log(rand_double())*temp;
bool accepted=state.modify(accept_diff);
if(accepted){
accept_cnt++;
if(best_state.score<state.score){
best_state=state;
cerr << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
update_cnt++;
}
}
}
cerr << "[result] " << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
return best_state;
};
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};
}
int calc_income(const vector<pii> &edges){
set<pii> st(all(edges));
array<array<pii,4>,N*N> g;
rep(i,N*N){
rep(k,4){
if(G[i][k]==-1){
g[i][k]={-1,INF};
}else{
if(st.contains({i,G[i][k]})||st.contains({G[i][k],i})){
g[i][k]={G[i][k],223};
}else{
g[i][k]={G[i][k],1000};
}
}
}
}
array<array<int,N*N>,N*N> dist;
array<array<int,N*N>,N*N> cnt;
rep(i,N*N){
dist[i].fill(INF);
cnt[i].fill(0);
priority_queue<pii,vector<pii>,greater<pii>> pq;
dist[i][i]=0;
pq.push({0,i});
while(!pq.empty()){
auto [d,x]=pq.top();
pq.pop();
if(dist[i][x]!=d) continue;
for(auto [y,c]:g[x]){
if(y==-1) continue;
if(chmin(dist[i][y],dist[i][x]+c)){
cnt[i][y]=cnt[i][x]+(c==223);
pq.push({dist[i][y],y});
}
}
}
}
int sum=0;
rep(i,K){
sum+=cnt[A[i]][B[i]];
}
return 60*sum;
}
namespace Solver{
struct State{
vector<pii> edges;
int score=0;
State(){
rep(i,N-1) edges.emplace_back(one(N/2,i),one(N/2,i+1));
rep(i,N-1) edges.emplace_back(one(i,N/2),one(i+1,N/2));
score=get_score();
}
int get_score(){
int sz=len(edges);
vector<int> income(sz+1,0);
vector<pii> now_edges;
rep(i,sz+1){
income[i]=calc_income(now_edges);
if(i==sz) break;
now_edges.push_back(edges[i]);
}
vector<vector<vector<int>>> dp(T+1,vector<vector<int>>(T+2,vector<int>(sz+1,-INF))); //[turn][協力者数][進行度]=所持金
dp[0][1][0]=M;
rep(t,T){
rep(i,T+2){
int cost=floor(1e7/sqrt(i));
rep(k,sz+1){
if(dp[t][i][k]<0) continue;
if(k+1<=sz&&cost<=dp[t][i][k]){
chmax(dp[t+1][i][k+1],dp[t][i][k]-cost+income[k+1]);
}
if(i+1<T+2) chmax(dp[t+1][i+1][k],dp[t][i][k]+income[k]);
chmax(dp[t+1][i][k],dp[t][i][k]+50000+income[k]);
}
}
}
int best_score=0;
rep(i,T+2){
replr(k,sz,sz+1){
chmax(best_score,dp[T][i][k]);
}
}
return best_score;
}
void output_ans(){
int sz=len(edges);
vector<int> income(sz+1,0);
vector<pii> now_edges;
rep(i,sz+1){
income[i]=calc_income(now_edges);
if(i==sz) break;
now_edges.push_back(edges[i]);
}
vector<vector<vector<int>>> dp(T+1,vector<vector<int>>(T+2,vector<int>(sz+1,-INF))); //[turn][協力者数][進行度]=所持金
vector<vector<vector<tii>>> pre(T+1,vector<vector<tii>>(T+2,vector<tii>(sz+1,{-1,-1,-1})));
dp[0][1][0]=M;
rep(t,T){
rep(i,T+2){
int cost=floor(1e7/sqrt(i));
rep(k,sz+1){
if(dp[t][i][k]<0) continue;
if(k+1<=sz&&cost<=dp[t][i][k]){
if(chmax(dp[t+1][i][k+1],dp[t][i][k]-cost+income[k+1])){
pre[t+1][i][k+1]={t,i,k};
}
}
if(i+1<T+2){
if(chmax(dp[t+1][i+1][k],dp[t][i][k]+income[k])){
pre[t+1][i+1][k]={t,i,k};
}
}
if(chmax(dp[t+1][i][k],dp[t][i][k]+50000+income[k])){
pre[t+1][i][k]={t,i,k};
}
}
}
}
int best_score=0;
int nt=-1,ni=-1,nk=-1;
rep(i,T+2){
replr(k,sz,sz+1){
if(chmax(best_score,dp[T][i][k])){
nt=T;
ni=i;
nk=k;
}
}
}
vector<tii> ans;
vector<int> income_v;
while(0<=nt){
auto [pt,pi,pk]=pre[nt][ni][nk];
if(pt==-1) break;
if(pk!=nk) ans.emplace_back(1,edges[pk].first,edges[pk].second);
else if(pi!=ni) ans.emplace_back(2,-1,-1);
else ans.emplace_back(3,-1,-1);
nt=pt;
ni=pi;
nk=pk;
income_v.push_back(dp[nt][ni][nk]);
}
reverse(all(ans));
reverse(all(income_v));
assert(len(ans)==T);
int idx=0;
for(auto [t,u,v]:ans){
int x,y;
cin >> x >> y;
assert(income_v[idx]==x);
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();
}
idx++;
}
}
bool modify(double accept_diff){
auto pre_edges=edges;
int r=rand_int(2);
if(r==0||edges.empty()){
edges.insert(edges.begin()+rand_int(len(pre_edges)+1),get_random_element(E));
}else{
edges.erase(edges.begin()+rand_int(len(pre_edges)));
}
int new_score=get_score();
//cerr << score << " " << new_score << endl;
if(accept_diff<=new_score-score){
score=new_score;
return true;
}else{
edges=pre_edges;
return false;
}
}
};
void solve(){
State state;
//state=SA<State,1500,0.>(state);
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);
}