結果
| 問題 | No.3453 Crape Shop |
| コンテスト | |
| ユーザー |
 Frest@競プロ
|
| 提出日時 | 2026-09-20 01:52:23 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 9 ms / 2,000 ms |
| + 207µs | |
| コード長 | 23,341 bytes |
| 記録 | |
| コンパイル時間 | 6,708 ms |
| コンパイル使用メモリ | 391,492 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-09-20 01:52:32 |
| 合計ジャッジ時間 | 8,936 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
ソースコード
#ifndef ONLINE_JUDGE//なんか手元ではデバックモードになって、atcoder上ではデバックモードにならないらしい ABC325Dはこれで通った
#define _GLIBCXX_DEBUG//[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4のデバックTLEなどに注意
#endif//これと上のONLINE JUDGEが絶対必要
//★TLEにならないはずなのにTLEになったらオンラインジャッジを消してデバックモードのまま提出をする。
#define _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS//これを消すとvisual studioがバグる
#define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS//これを消すとvisual studioがバグる
#include <bits/stdc++.h>
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
#include <atcoder/all>
using namespace atcoder;
//using mint = modint;//modを自分で設定したい場合に使う↓のset_modをする これを外側で書く
//mint::set_mod(m);//これでmがmodになる ABC282-E これをmain関数内で書く
using mint = modint998244353;//mintはchminができない
//using mint = modint1000000007;//mintはchminができない
using vmint = vc<mint>; using vvmint = vv<mint>; using vvvmint = vv<vmint>;
//mint im = mint(1)/m;//modの割り算はlogがかかるらしいから a/m をするなら a*imをすること。int/intをするとmintにしてくれないのでmint(int)/intとかにしないといけない。
//return (mint(x).pow(y) + mint(y).pow(x)).val();//ACLでmodpowを求めてからint型で返したいときに使う ABC282-E
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define nfor(i,s,n) for(ll i=s;i<n;i++)//i=s,s+1...n-1 ノーマルfor
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define dfor(i,s,n) for(ll i = (s)-1; i>=n;i--)//s-1スタートでnまで落ちる
#define nall(a) a.begin(),a.end()//ノーマルオール
#define rall(a) a.rbegin(),a.rend()//R入りオール
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define dame cout<<-1<<endl
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}// if(ans[i])YN;
#define cout(n) cout<<n<<endl;
#define Bit(n) (ll(1)<<(n))//1<<nにする、longlongじゃないとオーバーフローすることが多いのでこれを用意している
#define vc_unique(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define vc_rotate(v) rotate(v.begin(),v.begin()+1,v.end());//1回左方向にローテートするbegin,begin+回数,end 、回数の変数名をrotateとすると関数名と被るのでだめ ABC004-C
#define vc_reverse(v) reverse(v.begin(),v.end())//[begin,end)をreverseする、これには対応させてないけど(v.begin()+2,v.begin()+5)と書くと[2,5)の範囲をリバースする やるなら自分で書いて
#define yu_qurid(x,y) ((x)*(x)+(y)*(y))//ユークリッド距離 sqrtはしてないなので注意、(x座標の距離,y座標の距離)、defineってかいたやつを展開してるだけなので()がないとx1-x2とか入れると掛け算が優先されておかしくなる、√が二つあるときは√は消せないのでldでやるしかない ABC010-C
#define mannhattan(x1,x2,y1,y2) (abs(x1-x2)+abs(y1-y2)) // マンハッタン距離 = |x1-x2|+|y1-y2| 座標の絶対値の和
#define pop_cnt(s) ll(popcount(uint64_t(s)))
#define next_p(v) next_permutation(v.begin(),v.end())
//#define vvl_kaiten(v) {ll n = size(v);vvl nx(n,vl(n));rep(i,n)rep(j,n)nx[n-j-1][i]=v[i][j];swap(nx,v);}//vの配列を反時計周りに90°回転させる。「kaiten(v);」だけでvを回転できる、回転前のは消しちゃうから欲しいなら別の変数でもっておかないといけない、nを使っているけど変数被りとかは気にしなくていい、{}の中で書いているから問題ない
#define vvl_kaiten(v) {ll n = size(v);vvl nx(n,vl(n));rep(i,n)rep(j,n)nx[j][n-i-1]=v[i][j];swap(nx,v);}//時計回り版、回転はn*nじゃないとできないので注意
//#define vs_kaiten(v) {ll n = size(v);vs nx(n,string(n,'.'));rep(i,n)rep(j,n)nx[n-j-1][i]=v[i][j];swap(nx,v);}//文字列版 反時計回り
#define vs_kaiten(v) {ll n = size(v);vs nx(n,string(n,'.'));rep(i,n)rep(j,n)nx[j][n-i-1]=v[i][j];swap(nx,v);}//時計回り版、回転はn*nじゃないとできないので注意
#define vvl_tenti(v) {ll n = size(v);vvl nx(n,vl(n));rep(i,n)rep(j,n)nx[j][i]=v[i][j];swap(nx,v);}//転置する、n*nじゃないとできないので注意
#define vs_tenti(v) {ll n = size(v); vs nx(n, string(n,'.')); rep(i, n)rep(j, n)nx[j][i] = v[i][j]; swap(nx, v);}
//デバック用------------------
#define vc_cout(v){ll n = size(v);rep(i,n)cout<<v[i]<<endl;}//一次元配列を出力する、[i]として見ることによってcharとかlonglongを気にせず使える
#define vv_cout(v){ll n = size(v);rep(i,n){rep(j,size(v[i])){cout<<v[i][j]<<' ';}cout<<endl;}}//二次元配列を出力する、[i][j]として見ることによってcharとかlonglongを気にせず使える
//---------------------------
using ll = long long;
using ld = long double;//if文とかで一致判定をするとき、割り算をするならなるべくかけ算の形にした方がいい、かけ算なら誤差みたいなのが生まれないらしい ABC130-C
//using lll = __int128;//paizaとatcoderのジャッジだけ使える、visual studioは上の多倍長整数のlllを使ってください。
using bl = bool;
using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using vvvvl = vv<vvl>;
using vs = vc<string>; using vvs = vv<string>;
using vb = vc<bl>; using vvb = vv<bl>; using vvvb = vv<vb>;
using vld = vc<ld>; using vvld = vv<ld>; using vvvld = vv<vld>;
using P = pair<ll, ll>;
//pq<ll>q;
template<class T> using pq = priority_queue<T, vc<T>>;//★大きい順に取り出す コスト,頂点 bfs系で使う 小さい順じゃないですABC305E
template<class T> using pq_g = priority_queue<T, vc<T>, greater<T>>;//小さい順に取り出す ダイクストラ法で使う
using tup = tuple<ll, ll, ll>;//cout<<get<番号>(変数名)<<endl; cout<<get<0>(t)<<endl; auto [cost, l, r] = t;
//-----------------
ll pow2(ll x) { return x * x; };
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }//snukeさんのライブラリ集から貰ってきた
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<class T>T tousa_sum1(T l, T d, T r) {//初項,公差,末項 で総和を求める 負でも使える
T wide = (r - l) / d + 1;//(初項+末項)/公差+1 で項数を求める
return (l + r) * wide / 2;//((初項+末項)*項数)/2、長方形を半分にするやつ
}
template<class T>T tousa_sum2(T a, T d, T n) {//初項,交差,項数 で総和を求める、負でも正でも使える,1や-1の直書きintに注意
return (a * 2 + d * (n - 1)) * n / 2;////(初項+末項)*項数/2を元に変形する。末項って求めることができて、等差数列の一般項から、末項=初項+公差*(項数-1)となるので、これを代入する。そうすると総和=(初項+初項+(項数-1)*公差)*項数/2になる ABC190-D
}
ll kousa_kousuu(ll l, ll r, ll d) {//等差数列の項数を求める。求め方を知らなかったからただメモしておきたいだけではある() ABC190-D
return (r - l) / d + 1;//(末項-初項)/交差+1が項数を求める式。+1は初項のカウントができてないから+1するということ
}
//mint touhi_sum(mint a, mint r, ll n) {////等比数列の総和を返す、(初項、公比、項数)で、その初項から項数での総和を求める。a(r^n-1)/(r-1)。中途半端なやつが欲しいなら累積和みたいにやる。int系がいいなら型を自分で変える、だいたいmintだと思うけど ABC357-D。 ABC391-E
// //高校数学の美しい物語のページの公式をそのままコードにしただけ。だいたい値をくくるとこの公式が使えるみたいなイメージがある
// if (r == 1) {//公比が1のときだけ一生 *1 が続くのでこれだけ場合分けするらしい、aがn個あるときの総和となるのでa*nがそのまま答え
// return a * n;
// }
// mint bunsi = a * (r.pow(n) - mint(1));
// mint bunbo = r - 1;
// return bunsi / bunbo;//ABC357-Dみたいに値をくくって等比数列を作ったときは、そのくくった値を掛け算して戻すのを忘れないように注意
//}
ll take_mod(string& s, ll mod) {//文字列sについてmodでハッシュを取る。10^1000みたいな数字でもハッシュを取れることを忘れないでくれ ABC339-F
ll res = 0;
for (char c : s) {//一個ずつ文字を見ていく、計算量はO(文字数)かかる。「c - '0'」や「c - 'a'」にしてしまうと、そのハッシュの値は0となってしまい、"0000"と"0"や"aaaa"と"a"が同じになってしまうので注意
res = (res * 10 + ll(c)) % mod;//桁DPみたいに今までの余りを*10して今回のを足してそれに対して%modを取ると正しい答えになる
}
return res;
}
void string_chmax(string& a, string b) {//ABC118-Eみたいな「桁数が多ければ絶対勝ち」なやつはただのmaxでは仕様的にだめなのでそれ用のchmax
if (a.size() < b.size()) a = b;
else if (a.size() == b.size()) {
if (a < b) a = b;
}
}
vl toposo(vvl to) {//グラフのtoを渡してトポソ後の配列のサイズを返す、サイズがnじゃないなら矛盾ということになる。ABC223-Dはpq_gを使うのでpq_gにしているので注意。トポロジカルソートしつつ何かする問題が多めで、これは単純なトポソしかできない。
ll n = to.size(); vl cnt(n, 0); rep(i, n) { for (ll t : to[i])cnt[t]++; } pq_g<ll>q; rep(i, n)if (cnt[i] == 0)q.push(i); vl res; while (!q.empty()) { ll i = q.top(); q.pop(); res.pb(i); for (ll t : to[i]) { cnt[t]--; if (cnt[t] == 0)q.push(t); } }return res;
}
ll nc2(ll x) { if (x < 2)return 0; return x * (x - 1) / 2; }//幅1のときは、nc2(w+1)なので注意。wのままだと幅1を許していないので半開区間にしないといけない。0通りは弾かないといけない ABC200-E
ll nc3(ll x) { if (x < 3)return 0; return x * (x - 1) * (x - 2) / 6; }
//----------------
vl dx = { 1,0,-1,0 };//vl dx={1,1,0,-1,-1,-1,0,1};
vl dy = { 0,1,0,-1 };//vl dy={0,1,1,1,0,-1,-1,-1};
//ハニカムでの移動 6方向あって、今のi%2の値によって変わる、ハニカムの図に番兵を入れるとその分だけずれるので注意 JOIイルミネーション
vl dy_hani = { -1,-1,0,1,1,0 };//y軸はどっちも同じ
vl dx0_hani = { 0,1,1,1,0,-1 };//i%2=0のx軸の移動
vl dx1_hani = { -1,0,1,0,-1,-1 };//i%2=1のx軸の移動
const ll INF = 2e18;
//ll D = 61;//ダブリングの桁 2^61ならINFが収まってくれる ARC60-E
//if(regex_match(s, regex("")))YN;//ABC349みたいな10^5くらいの長さに正規表現を使おうとするとTLEするっぽい？https://twitter.com/Not_Leonian/status/1779893867606913405
//scanf("%d.%d", &b, &c);//2.345みたいな小数を「.」区切りで受け取る 小数の切り捨てとかでめんどうなら*100とかして下駄をはかせて最後に/100するABC169-C
//ll(1)<<60 2^60>1e18
//bool operator>(const edge& a, const edge& b) const{//pq_gは>、pqは<、普通のソート、rソートも< pq_gのoperatorはstruct内に書くとエラーみたいなので外に書く。引数の型や{}を書く前に必ずconstを書かないとエラーになる
// return a.dist > b.dist;//距離だけ見たけどこれでよかったみたい、ワンチャン寒さと暑さのデータも比較するかと思ったけどいらないみたい
//}
//bool operator<(const state& R) const {
// // a -> b -> c -> d の優先順位で比較する
// return std::tie(a, b, c, d) < std::tie(R.a, R.b, R.c, R.d);
//}
//structの初期化のやつで引数をそのままa(a)みたいなのを書かないときは「:」がいらない、edge(ll a){処理}みたいな感じ ABC330-F
//sort(nall(v), [](P a, P b) {//ソートの比較関数は>か<のどっちかじゃないとだめ、nallとrallはどっちでもうまくいく
// return a.first * b.second < a.second * b.first;
// });
//tupleだと何個でもいけて型が違うのも可能。ただ、[i]とか.firstみたいなのが一切なくてauto[a,b,c...]=tupをしないと中身が見れないから注意。型の違う複数個はstructが安定
using P2 = array<P, 2>;//ABC339-D めちゃくちゃ早くなる 初期化しないとメイン関数でも適当な値が入ってるので注意 P2 ar{P(0,0),P(0,0)};
using ar2 = array<ll, 2>;//配列に突っ込むときは vec.eb(ar{0,1}); で{}で中身を書かないとだめ 初期化子がどうたらというエラーになる
using ar3 = array<ll, 3>;
//------------------------------------------
template<class T>istream& operator>>(istream& i, vc<T>& v) { rep(j, size(v))i >> v[j]; return i; }//なんか入力ができるすごいやつsnukeさんから盗んだ、何次元だとしても突っ込めばやってくれる原理不明、その配列のそれぞれのサイズにぴったり入る？ように入力を受け取る、つまりサイズがばらけててもいい感じに入れてくれる
void print(ld x) { printf("%.20Lf\n", x); }//10桁だと足りない問題があったABC26-D 調べた感じ20桁までなら大丈夫っぽい
void mukou_debug(vvl to, bool yukou) {//GRAPH × GRAPH用の無向グラフを出力する、pairにしたいなら型を変えてくれ
ll n = size(to); ll cnt = 0;//辺の本数
vc<pair<ll, ll>>v; rep(i, n)for (ll t : to[i]) if (i < t || yukou)cnt++, v.eb(i + 1, t + 1);//有向グラフなら全部OK、違うなら無向なのでf<tのみ見る、using Pのやつを別のにしたいときのためにPを使わずにpair<ll,ll>にしてる
cout << n << ' ' << cnt << endl; for (auto [f, t] : v)cout << f << ' ' << t << endl;
}
bool out_grid(ll i, ll j, ll h, ll w) {//trueならcontinueにしてほしい、falseなら無視でいい if(out_grid(ni,nj,h,w))continue;とやる
return (!(0 <= i && i < h && 0 <= j && j < w));
}
struct edge {
ll to, cost;
ll id;//いらないなら使わない
edge(ll to, ll cost, ll id = 0) :to(to), cost(cost), id(id) {}
};
////遅延セグ木用テンプレ、変更系クエリのminを求めるやつとする、変更系じゃないなら、新しいやつが初期化と一致してるかの判定はせずにminなりmaxなりを返す ABC179-F
//ll op(ll a, ll b) { return min(a, b); }
//ll e() { return INF; }
//ll mapping(ll a, ll b) {//左が関数、右がセグ木
// //return a * b.wide;//区間に和を加算したいとき、一番下の各サイズ1に加算させたいなら、この上の段階ではそのサイズ分かけ算しないと、そのサイズ2以上のときに対応できない。seg.set(i)みたいな感じでサイズ1のを見れば、applyしたのがそれぞれ一番下に伝播してくれるけど、それをしてもprodしたときのまとめて見るタイミングだと幅2以上の場所では、かけ算しないと一個分の値にならない。ABC462-D
//
// //return min(a,b);//絶対更新優先じゃなくてただのminならこれを使う
// if (a == INF)return b;//ACLの遅延セグ木は関数を渡されてなくても一旦もってる関数を適応させる。持ってない場合はidの値をもっているとして適応されるから、それ対策をしないといけない
// return a;//aがidじゃないならあとから来た方が優先されるからaを返す
//}
//ll composition(ll a, ll b) {//左が新しい関数、右が古い関数
// //return min(a, b);//この問題はminじゃないとだめだった、サンプル1のクエリ1とクエリ3で、後から来たクエリ3の値が優先されてはいけなかった...orz 1時間くらいかかった...
// if (a == INF)return b;//ACLの遅延セグ木は関数を渡されてなくても一旦もってる関数を適応させる。持ってない場合はidの値をもっているとして適応されるから、それ対策をしないといけない
// return a;//aがidじゃないならあとから来た方が優先されるからaを返す
//}
//ll id() { return INF; }
//lazy_segtree<ll, op, e, ll, mapping, composition, id>seg(n);
//-------------------------------------------------------------
////遅延セグ木用テンプレ2。セグ木上の区間総和と、関数の区間"代入"をする。関数は必ず代入（代入とかけ算を両立はもしかしたらできるかも、0,1,2とか代入きたら強制代入で、そうじゃないならかけ算など、無の関数は-1のクエリなどにする） ABC417-F
//struct S {//セグ木の内部
// ll w;//今見て居るやつの幅。複数個のiを包含しているセルについて、そこを求めるためにwがないと求められない。総和なのにiが一個分しかないとかよくあるから注意。
// mint sum;//今見て居るセルの期待値の総和
//};
//S op(S a, S b) { return S(a.w+b.w,a.sum+b.sum); }//区間加算で区間総和求めるときとか、(加算値*w)しないとそこのセルが正しく総和にならないやつに注意
//S e() { return S(0, 0); }//無
//struct F {//関数
// bool change;//代入の関数か。仕様上、無のやつが投げられることがあるからそれを対策しないといけない。
// mint x;//代入したい値
//};
//S mapping(F a, S b) {//左が関数、右がセグ木
// if (a.change) {//代入がきたから強制
// return S(b.w, a.x * b.w);//このセルについて、セグ木上でこのセルの正しい答えにしないといけないから、幅がないとダメ。ここのセルはそこを含むiの期待値の総和
// }
// return b;//無の関数がきたって感じ、なので何もせずに返す
//}
//F composition(F a, F b) {//左が新しい関数、右が古い関数
// if (a.change)return a;//falseなら無の関数なので無視
// return b;
//}
//F id() { return F(false, 0); }//falseにしておけばOK
////lazy_segtree<S, op, e, F, mapping, composition, id>seg(n);
//auto erase = [&](ll y, ll x) {//(y,x)を削除する ABC370-D
//
//};
//O(5*10^8)までならTLEしない(配列はMLEする) https://atcoder.jp/contests/abc381/submissions/60233818
//後ろから求めるという発想を忘れやすい。発想を出せればよいわけではなく、後ろから見ることによって問題の解法にとって何のメリットがあるか？を考えないと解法に派生しないので注意 ABC372-D
//DPの本質は貰うDPで、貰うDPじゃないと解けない問題がたくさんある 期待値DPやABC370-E
//a,bという変数があったとして、a→bという移動とb→aという移動の実装をするとき、swapすることで楽に実装できる ABC369-E,ABC376-B なおABC376-Fみたいなのはswapできない
//区間の問題のとき、とりあえずLかRを固定する ABC377-D
//bool operator<(const ll a)const{ return ????;}
//string(個数,文字);
//s.substr(始点インデックス,始点から取る個数);//O(サイズ)かかるので注意 ICPC2025-D
//loga(b)は底の変換公式より、「log(b)/log(a)」のコードで求められる。log(x)はloge(x)を表す。任意の底をするなら、変換公式を使う、カッコの中が上
//string s = to_string(数字); ll k = stoll(string); ←stolだとlong型になる使わない。stoiはint
//ll it = lower_bound(nall(v),値,greater<ll>())-v.begin(); //配列のやつそのままで降順に対してサーチできる ABC389-F
//ans -= (条件 ? trueのときの値 : falseのときの値);
//「O(2^29)」「O(3^18)」「O(4^14)」「O(5^12)」「O(12!)」までの計算量ならぎりぎりTLEしない(定数倍やlogなどが少しでも入ったら、左の数字だとTLEする、だいたいO(10!)かO(2^16)かO(2^20)くらいが多い)
//10^9以下での素数砂漠は281 ABC152-E(アルゴ式より)
//if (s.find(t) != string::npos)return true;//O(|s|*|t|)。s.find(t)で、文字列sの各場所を始点として、文字列tと一致しているかを調べてくれる。みつからなかったらnpos的な値を返してくれるので!=のときは見つかったとなる。愚直に調べるやつを関数化してくれてると思えばいい。ABC305-G。rep(i,n-m+1)rep(j,m)if(s[i+j]!=t[j])的な感じのあれということ
//「lowerとupperでごちゃごちゃしてたら、自分で答えを二分探索を書いた方が事故らない」 ABC155-D
//愚直の考えて高速化を考える
//ロリハできる場合はz-algorithmができる場合がある、後者の方が実装が事故らない zをやるとき'$'関係でおかしくなる ABC430-E https://atcoder.jp/contests/abc418/submissions/71222019
//特殊な操作→超頂点として扱う ABC463-E
//区間スケジューリング的なのは基本は(R,L)でソート ABC463-D
//x以下にある平方数を数えるなら最大値を作ってからll(sqrtl)をすればいい ABC428-D
//aを決め打ちしたらbが一意とか、a,bを一緒にセットで決め打ちできるとかの発想 ABC453-E ABC458-E
//一番右を基準にして、左にある個数を見てあげると実質的に2つの決め打ちができる ABC405-E
//直接的に解法の答えが求められなくても、簡単に求められる値から、何か引き算したらつながる可能性がある ABC458-E(いもす法の値から、両方いける値を式変形から条件を求める）
//2べき包除原理
//パターン1：求めたい答えが「1つも条件を満たさない（0個）」の場合
//1が条件を満たすことを強制
//0は自由
//パターン2：求めたい答えが「全ての条件を満たす（全部）」の場合 ABC003 - D
//1が条件に違反することを強制
//0は自由
//------------------------------------------
P op_max(P a, P b) {
return max(a, b);
}
P e_max() {
return P(-1, -1);
}
P op_min(P a, P b) {
return min(a, b);
}
P e_min() {
return P(INF, INF);
}
void solve() {
/*
超頂点
楽な実装がわからなかったが
超頂点的に配列をもつんじゃなくて
単に文字の上にいたら遷移先を見ればいいのか
*/
ll n, a, b;
cin >> n >> a >> b;
rep(i, n) {
ll p;
cin >> p;
if (p == 1) {
a--;
}
if (p == 2) {
b--;
}
if (p == 3) {
a--; b--;
}
if (a < 0 || b < 0) {
cout << i + 1 << endl;
return;
}
}
dame;
}
int main() {
//ll t;
//cin >> t;
//rep(ti, t)solve();
solve();
}