abc217 E-sorting queriesにおいて自分のコードのどこが間違っているのかがわからないです。協力していただけると幸いです。

Question

実現したいこと

コード内の間違えを見つけていただきたいです。

発生している問題・分からないこと

16個のtest caseのうち5個がwaです。

エラーメッセージ

エラーメッセージは出ていないです。

該当のソースコード

#include <bits/stdc++.h>
#include <cmath>
using ll=long long;
#define rep(i,a,b) for(i=a;i<b;i++)
#define chmin(x,b) x=min(x,b)
using namespace std;
using v=vector<int>;
using vv=vector<vector<int>>;
int mod1=998244353;
int mod2=1000000007;
const ll INF = 1e18; 

int main(){
    ll n,q,y,x,i,j,k,z,p;
    int ans=1e9,sum2=0,h=0,w=0,m,h1=0,w1=0;
    ll tmp1=0,tmp2=0,sum=0;
    cin>>q;
    deque<int> deq;
    set<int>sat;
    rep(i,0,q){
        cin>>x;
        if(x==1){
            cin>>y;
            deq.push_back(y);
        }else if(x==2){
            if(sat.size()){
                auto ch=sat.begin();
                cout<<*ch<<endl;
                sat.erase(*ch);
                auto chh=sat.begin();
                //cout<<"*"<<*chh<<endl;
            }else{
                cout<<deq.front()<<endl;
                deq.pop_front();
            }
        }else{
            while(deq.size()){
                sat.insert(deq.front());deq.pop_front();
            }
        }
    }
    }

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

waがでたtest caseをみて自分なりにdebugをしたのですがなぜwaが出るのか原因を特定できませんでした。atcoder公式が出している解答コードを見たのですが同じようなコードを書いてあるように感じました。

問題のリンクです。
https://atcoder.jp/contests/abc217/tasks/abc217_e

解答コードを添付しておきます。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main() {
int Q;
cin >> Q;
priority_queue<int,vector<int>,greater<int>> pq;
queue<int> q;
rep(qi,Q) {
int c;
cin >> c;
if (c == 1) {
int x;
cin >> x;
q.push(x);
} else if (c == 2) {
if (pq.size()) {
cout << pq.top() << endl;
pq.pop();
} else {
cout << q.front() << endl;
q.pop();
}
} else {
while (q.size()) {
pq.push(q.front());
q.pop();
}
}
}
return 0;
}

補足

特になし

Comments

[fana]

全く使わない using とか define とか変数とか……
ご自身がご自身のためだけにコードを書いている分には好きにやればよかろうとは思いますが，
他者にコードを見せるとなった時点で，少しは不要な雑音を取り除こうとか思わないのでしょうか．

[fana]

> 自分なりにdebugをした

のであれば，問題が再現する入力くらいは示すべきでは．
「こんな単純なのでも動かない」という最小に近い入力例を．

Answer 1

fana さんの回答でも解決しないようなので、蛇足だとは思いますが補足させていただきます。

以下の入力に対して、

6
1 1
1 1
1 2
3
2
2

正しい出力は以下ですが、

1
1

ご提示のコードだと以下が出力されます。

1
2

原因は既に fana さんがおっしゃっている通りで、setには同じ値を複数登録できないからです。

同じ値を複数登録できるmultisetに変更したうえで、削除をイテレータによる位置指定で行うようにすれば、WAが無くなります。(削除を値で行おうとすると、同じ値がまとめて削除されてしまう)

    ll tmp1=0,tmp2=0,sum=0;
    cin>>q;
    deque<int> deq;
-   set<int>sat;
+   multiset<int>sat;
    rep(i,0,q){
        cin>>x;
        if(x==1){

            if(sat.size()){
                auto ch=sat.begin();
                cout<<*ch<<endl;
-               sat.erase(*ch);
+               sat.erase(ch);
                auto chh=sat.begin();
                //cout<<"*"<<*chh<<endl;
            }else{

Answer 2

set<int>sat;

何故set を使うのですか？
同じ値が複数個入力されてきたらまずいのではないのですか？

解答コードを見たのですが同じようなコードを書いてある

「同じような」　と　「同じ」　は違うわけで．
見た目の雰囲気が何となく似ていればそれで同じ動作結果になるわけではないです．
「同じ」と言えないのであれば，そこに存在する差分に着目してください．