結果

問題 No.2519 Coins in Array
ユーザー Nzt3
提出日時 2023-10-27 22:36:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 1,869 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 207,624 KB
最終ジャッジ日時 2025-02-17 15:28:06
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
pair<ll,vector<array<int,2>>>dfs(vector<ll> v){
assert(!v.empty());
if(v.size()==1){
return make_pair(v[0],vector<array<int,2>>());
}
int N=v.size();
vector<array<int,2>>ret;
ll m=1e18;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
vector v2(0,0ll);
for(int k=0;k<N;k++){
if(k!=i&&k!=j)v2.push_back(v[k]);
}
if(gcd(v[i],v[j])!=1)v2.push_back(0);
else v2.push_back(v[i]*v[j]-v[i]-v[j]+1);
auto [n,rv]=dfs(v2);
if(n<m){
m=n;
rv.push_back({i+1,j+1});
ret=rv;
}
}
}
return make_pair(m,ret);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin>>N;
vector A(N,0ll);
int idx1=-1;
for(int i=0;i<N;i++){
cin>>A[i];
if(A[i]==1){
idx1=i;
}
}
if(idx1==-1){
if(N<4){
auto [m,v]=dfs(A);
reverse(v.begin(),v.end());
cout<<m<<'\n';
for(auto i:v)cout<<i[0]<<' '<<i[1]<<'\n';
}else{
cout<<"0\n";
vector odd(0,0),even(0,0);
for(int i=0;i<N;i++){
if(A[i]%2){
odd.push_back(i);
}else{
even.push_back(i);
}
}
while(even.size()<2){
int k1=odd.back();
odd.pop_back();
int k2=odd.back();
odd.pop_back();
for(int &i:even){
if(i>k1)i-=1;
}
for(int &i:even){
if(i>k2)i-=1;
}
even.push_back(odd.size()+even.size());
cout<<k1+1<<' '<<k2+1<<'\n';
}
cout<<even[0]+1<<' '<<even[1]+1<<'\n';
for(int i=odd.size()+even.size()-1;i>1;i--){
cout<<i<<" 1\n";
}
}
}else{
cout<<"0\n";
if(idx1==0){
cout<<"1 2\n";
}else{
cout<<idx1+1<<" 1\n";
}
for(int i=N-1;i>1;i--){
cout<<i<<" 1\n";
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0