結果
問題 | No.2519 Coins in Array |
ユーザー |
👑 |
提出日時 | 2023-10-27 22:42:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 2,528 bytes |
コンパイル時間 | 3,544 ms |
コンパイル使用メモリ | 253,024 KB |
最終ジャッジ日時 | 2025-02-17 15:31:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; using namespace atcoder; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; typedef vector<vector<int>> vvi; typedef vector<vector<long long>> vvl; typedef long double ld; typedef pair<int, int> P; template <int m> std::ostream& operator<<(std::ostream& os, const atcoder::static_modint<m>& a) {os << a.val(); return os;} template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template <typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} int main(){ int n; cin >> n; vl a(n); cin >> a; auto func = [&](ll x, ll y){ if(x == 0 or y == 0) return (long long)0; ll g = gcd(x, y); if(g >= 2) return (long long)0; else return (x - 1) * (y - 1); }; if(n >= 4){ vi e; vi o; rep(i, n){ if(a[i] % 2 == 0){ e.push_back(i); if(int(e.size()) >= 2 and int(o.size()) >= 4) break; }else{ o.push_back(i); if(int(e.size()) >= 2 and int(o.size()) >= 4) break; } } cout << "0\n"; if(int(e.size()) >= 2){ cout << e[0] + 1 << ' ' << e[1] + 1 << "\n"; rep(i, n - 2){ cout << 1 << ' ' << n - 1 - i << "\n"; } return 0; } if(int(e.size()) == 1){ cout << o[0] + 1 << ' ' << o[1] + 1 << "\n"; int cnt = 0; if(o[0] < e[0]) cnt++; if(o[1] < e[0]) cnt++; e[0] -= cnt; cout << e[0] + 1 << ' ' << n - 1 << "\n"; rep(i, n - 3){ cout << 1 << ' ' << n - 2 - i << "\n"; } return 0; } cout << o[0] + 1 << ' ' << o[1] + 1 << "\n"; o[2] -= 2; o[3] -= 2; cout << o[2] + 1 << ' ' << o[3] + 1 << "\n"; cout << n - 3 << ' ' << n - 2 << "\n"; rep(i, n - 4){ cout << 1 << ' ' << n - 3 - i << "\n"; } return 0; } vi perm(n); rep(i, n) perm[i] = i; vi ans_perm = perm; ll ans = 1001001001001001001; do{ long long tmp = 0; if(n == 2) tmp = func(a[perm[0]], a[perm[1]]); if(n == 3) tmp = func(func(a[perm[0]], a[perm[1]]), a[perm[2]]); if(tmp < ans){ ans = tmp; ans_perm = perm; } }while(next_permutation(perm.begin(), perm.end())); cout << ans << "\n"; cout << ans_perm[0] + 1 << ' ' << ans_perm[1] + 1 << "\n"; if(n == 3) cout << "1 2\n"; return 0; }