結果
問題 | No.2519 Coins in Array |
ユーザー |
![]() |
提出日時 | 2023-10-27 23:33:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 10,900 bytes |
コンパイル時間 | 2,282 ms |
コンパイル使用メモリ | 210,512 KB |
最終ジャッジ日時 | 2025-02-17 16:07:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include<bits/stdc++.h>#define PPque priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>>#define Pque priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>#define pque priority_queue<ll, vector<ll>, greater<ll>>#define umap unordered_map#define uset unordered_set#define rep(i, s, f) for(ll i = s; i <= f; i++)#define per(i, s, f) for(ll i = s; i >= f; i--)#define all0(x) (x).begin() ,(x).end()#define all(x) (x).begin() + 1, (x).end()#define vvvvl vector<vvvl>#define vvvi vector<vector<vector<int>>>#define vvvl vector<vector<vector<ll>>>#define vvvc vector<vector<vector<char>>>#define vvvd vector<vector<vector<double>>>#define vvvm vector<vector<vector<mint>>>#define vvi vector<vector<int>>#define vvl vector<vector<ll>>#define vvs vector<vector<string>>#define vvc vector<vector<char>>#define vvp vector<vector<pair<ll, ll>>>#define vvb vector<vector<bool>>#define vvd vector<vector<double>>#define vvm vector<vector<mint>>#define vp vector<pair<ll, ll>>#define vi vector<int>#define vl vector<ll>#define vs vector<string>#define vc vector<char>#define vb vector<bool>#define vd vector<double>#define vm vector<mint>#define P pair<ll, ll>#define TU tuple<ll, ll, ll>#define rrr(l, r) mt()%(r-l+1)+l#define ENDL '\n'#define ull unsigned long longtypedef long long ll;using namespace std;//////////////////////////////////////////////////////////////////////////////////////////////////////////////これが本当の組み込み関数ってね(笑)template <typename T>T or_less(vector<T> &A, T x) { //x以下で最大要素の添字 前提: sort済み 存在しない: -1return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1);}template <typename T>T under(vector<T> &A, T x) { //x未満の最大要素の添字 前提: sort済み 存在しない: -1return distance(A.begin(), lower_bound(A.begin(), A.end(), x)-1);}template <typename T>T or_more(vector<T> &A, T x) { //x以上で最小要素の添字 前提: sort済み 存在しない: N . //distanceのA.beginは添字を出すために常にA.begin() NG: A.begin() + 1return distance(A.begin(), lower_bound(A.begin(), A.end(), x));}template <typename T>T over(vector<T> &A, T x) { //xより大きい最小要素の添字前提: sort済み 存在しない: Nreturn distance(A.begin(), upper_bound(A.begin(), A.end(), x));}template <typename T>vector<T> vec_shift_right(vector<T> A, ll step, ll dir = 1, ll indexed = 1) {//dir = 1 : 右シフト dir = -1 : 左シフトll N = A.size() - indexed;vector<T> res(N+1);rep(i, indexed, N) {ll idx = i - step * dir;if(idx < indexed) idx += N;if(idx > N) idx -= N;res.at(i) = A.at(idx);}return res;}template <typename T>void UNIQUE(vector<T> &A) {sort(all0(A));return A.erase(unique(A.begin(), A.end()), A.end());}template <typename T>void rev90(vector<vector<T>> &A, int indexed = 1) {reverse(A.begin() + indexed, A.end());int n = A.size();rep(i, indexed, n-1) {rep(j, i+1, n-1) {swap(A.at(i).at(j), A.at(j).at(i));}}}void chmin(ll &a, ll b) {a = min(a, b);}void chmax(ll &a, ll b) {a = max(a, b);}////////////////////////////////////////////////////////////////////////数学系///////////////////////////////////////////////////////////////////////ll round(ll x, ll i) {return ll(x + 5 * pow(10, i-1))/ll(pow(10, i)) * ll(pow(10, i));}vp insu_bunkai(ll N) {vp res;for (ll i = 2; i * i <= N; i++) {ll cnt = 0;while(N % i == 0) {cnt++;N /= i;}if(cnt != 0) res.push_back(P(i, cnt));}if(N != 1) res.push_back(P(N, 1));return res;}ll extgcd (ll a, ll b, ll &x, ll &y) {if(b == 0) { x = 1;y = 0;return a;}ll d = extgcd(b, a%b, y, x);y -= a/b * x;return d;}template <typename T>T ceil(T a, T b) {assert(b != 0);if(a % b == 0) return a / b;if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;else return a / b;}template <typename T>T floor(T a, T b) {assert(b != 0);if(a % b == 0) return a / b;if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;else return a/b - 1;}ll modpow(ll x, ll y, ll mod) {if(x > mod) x %= mod;if(y == 0) return 1;ll res = modpow(x, y >> 1, mod);res = res * res % mod;if(y & 1) res *= x, res %= mod;return res;}ll sqrt_(ll a) {ll l = 0;ll r = 3000000000LL;while(l < r) {ll mid = (l + r + 1) / 2;if(mid * mid <= a) l = mid;else r = mid - 1;}return l;}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////グローバル変数を置くところ(情報工学意識高め)//#pragma GCC optimize("O3")//#pragma GCC optimize("unroll-loops")const ll int_max = 1001001001;const ll ll_max = 1001001001001001001LL;const double pi = 3.141592653589793;vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; // (番兵) → ↓ ← ↑ ※ 右から時計回りvl dy{0, 0, -1, 0, 1, 1, -1, -1, 1};//const ll mod = 1000000007;//const ll mod = 998244353;///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////*互いに素 : (A[i] - 1) * (A[j] - 1)以上の任意の数字が作れう。 F(i, j) = (A[i] - 1) * (A[j] - 1)互いに素でない : F(i, j) = 0一度0が作れれば、すべて0互いに素でないのが一つでも途中でも作れれば0それ、偶数奇数じゃ駄目ですか?N = 2は無視偶だけの時 : 0奇数だけの時 : 奇数と奇数で偶数, 偶 : 木 全探索N >= 4の時き と き、*/struct LazySegTree {vector<ll> dat;int size = 1;vector<ll> lazy;LazySegTree(int N) {while(size < N) {size *= 2;}/*初期値をどうするのかは状況によって変わるよね*/dat.assign(size*2, 0);lazy.assign(size*2, 0);}void evaluate(int u, int l, int r) {//本人と一個下を更新if (lazy.at(u) != 0) {/*lazyを受けてどう更新するの?例:dat.at(u) += lazy.at(u);*/dat.at(u) += lazy.at(u);if (r - l > 1) {/*それが根でないならばどうやってlazyを伝播させるの?例: lazy.at(u*2) += lazy.at(u)/2; lazy.at(u*2+1) += lazy.at(u)/2;*/lazy.at(u * 2) += lazy.at(u)/2; lazy.at(u * 2 + 1) += lazy.at(u)/2;}lazy.at(u) = 0;}}void update(int l, int r, int a, int b, int u, ll x) {//加算/更新...etc 完全に含まれないならば、下の方を更新した上で最新の値を代入evaluate(u, a, b);if (r <= a || l >= b) {//範囲外return ;}if (l <= a && b <= r) {/*完全に含まれる時、lazyをどうするのか例:lazy.at(u) += x * (b-a); evaluate(u, a, b);*/lazy.at(u) += x * (b-a); evaluate(u, a, b);return ;}int m = (a+b)/2;update(l, r, a, m, u*2, x);update(l, r, m, b, u*2+1, x);/*下二つが最新になった時、親はどうすれば最新になるか例:dat.at(u) = dat.at(u*2) + dat.at(u*2+1);*/dat.at(u) = dat.at(u * 2) + dat.at(u * 2 + 1);}ll query(int l, int r, int a, int b, int u) {//値を答えるための関数(update以外)l >= r の時、範囲外の時のやつを返すif (r <= a || l >= b) {/*範囲外の時何をしますか?例: return -10000;*/return 0;}evaluate(u, a, b);if (l <= a && b <= r) {return dat.at(u);}int m = (a+b)/2;ll L = query(l, r, a, m, u*2);ll R = query(l, r, m, b, u*2+1);/*下二つの値を受け取って、上をどうしますか?例: return max(L,R); */return L + R;}void add(int l, int r, ll x) {update(l, r + 1, 1, size+1, 1, x);}ll get(int l, int r) {return query(l, r + 1, 1, size +1, 1);}};void solve() {ll N;cin >> N;vl A(N+1);rep(i,1,N)cin >> A[i];vl os;vl es;auto f = [](ll a, ll b) {if(gcd(a, b) != 1) return 0LL;else return (a-1) * (b-1);};auto f2 = [&](vector<ll> B) {cout << f(B[1], B[2]) << endl;cout << 1 << " " << 2 << endl;return ;};if(N <= 3) {if(N == 2) {f2(A);return;}else {ll t1 = f(f(A[1], A[2]), A[3]);ll t2 = f(f(A[1], A[3]), A[2]);ll t3 = f(f(A[2], A[3]), A[1]);if(t1 <= t2 && t1 <= t3) {cout << t1 << endl;cout << 1 << " " << 2 << endl;cout << 1 << " " << 2 << endl;}else if(t2 <= t1 && t2 <= t3) {cout << t2 << endl;cout << 1 << " " << 3 << endl;cout << 1 << " " << 2 << endl;}else {cout << t3 << endl;cout << 2 << " " << 3 << endl;cout << 1 << " " << 2 << endl;}return ;}}rep(i,1,N) {if(A[i]%2==1)es.push_back(i);else os.push_back(i);}//esが偶数LazySegTree hosei(N);ll m = N;cout << 0 << endl; ///答えは0if(os.size() == 1) {cout << es[0] << " " << es[1] << endl;hosei.add(es[0], N, -1);hosei.add(es[1], N, -1);cout << os[0] + hosei.get(os[0], os[0])<< " " << N-1 << endl;m -= 2;}else if(os.size() == 0) {cout << es[0] << " " << es[1] << endl;hosei.add(es[0], N, -1);hosei.add(es[1], N, -1);cout << es[2] + hosei.get(es[2], es[2]) << " " << es[3] + hosei.get(es[3], es[3]) << endl;cout << N-3 << " " << N-2 << endl;m -= 3;}else {cout << os[0] << " " << os[1] << endl;m--;}while(m >= 2) {cout << 1 << " " << m << endl;m--;}}//無断で0を平方数にカウントする人もいる//”部分文字列”と”連続部分文字列”は違うので確認すること//一般のグラフと、有向辺かつその貼り方に制約がある(多くの場合:番号がで解放に伸びる)はだいぶ違うので確認すること//座標を2で割った時の”切り捨て側(左側)”を求めるには 誤:(x / 2) マイナスの時!!! 正:floor<ll>(x, 2);//stringでの数字の下から1桁目は 正:S.at(N-1) 誤:S.at(0)//if(S.at(i) == 1) ← charなのに1...?// modは取りましたか...?(´・ω・`)//sortの比較関数は、 a == b ならば falseを返す必要がある(そうで無いとRE(発生しない場合もある))int main() {ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(15);ll T = 1;//cin >> T;rep(i, 1, T) {solve();}return 0;}