以下の問題について解いていました
問題
要約すると、Pの値ごとにYをソートできれば良いという問題です
模範解答のコードでは以下のようになっています(少し変更してます)
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n,m; cin>>n>>m; ll p[m],y[m]; vector<ll>py[m]; for(int i=0;i<m;i++)cin>>p[i]>>y[i]; for(int i=0;i<m;i++)py[p[i]].push_back(y[i]); for(int i=0;i<n;i++)sort(py[i+1].begin(),py[i+1].end()); for(int i=0;i<m;i++){ printf ("%012lld\n",ll(p[i])*1000000+ int(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin())+1); } }
例えば入力例1
2 3
1 32
2 63
1 12
のとき、pyはpごとにソートされているので、
py[1]={12,32} py[2]={63}
という風になっていると思います
出力ではまず、py[p[i]]内でlower_boundでy[i]以上のイテレータを返すので、初めは32を返すと思います
その後のpy[p[i]].begin()+1では、py[p[i]]のうちの初めの要素に1足したものが返ってくるのでpy[i]の最初の要素12+1の13が返ってきて、結果は32-13=19となってしまうように思います
しかし実際はそうはなっていないのでどこかで私が解釈を誤っているのだと思うのですが、どこだか分かりません
また、何が起きているのか確かめようとして以下のようなコードを追加したのですが
for(int i=0;i<m;i++){ printf("%d",ll(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]))); }
invalid castのエラーが出てしまいます
vectorはlong long int型にキャストできないというような内容のようですが、上記の模範解答はOKで、そこから-py[p[i].begin()の部分を抜いた出力は不適切となるのはどうしてでしょうか
またこの問題自体についてですが、pごとにyをソートしていくのは、普通のC言語のように配列を使って制限時間内に(2重ループ使用なしで)解くことは可能でしょうか
どれか1つについてで良いので、もしよければ回答よろしくお願いします
追記:イテレータについて勘違いしていたようです
注意深く調べたところ
*lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]) なら中身の数値
lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]) なら数値の番地
lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin() なら「数値の番地-先頭の数値の番地」すなわち「数値が何番目か」
ということであると分かりました
出力に関してもキャストを外したところ無事実行でき、上記のそれぞれを自分で確認できました
要はこちらの不注意でした、申し訳ありません。また、ご指摘いただいた方は有難うございました
一応、普通の配列でもできないかどうか少し気になっているので質問は数日間残しておきます(回答がつかなければそのまま自己解決という形にさせていただきます)
配列を使った方法は、pについてクイックソートを使うときにその数字が元々何番目だったかなどの情報を保持しておけばいけるのではないかと考えたのですが、私の実装力では試せませんでした
追記2:何度もすみません
上述のプログラムについて、vector<ll>py[m];をvector<ll>py[100001];に変えたところ正解扱いになったのですが
vector<ll>py[m];のままだといくつかのテストケースで実行時エラーとなってしまいました
pyにpushしていくデータ数はmで間違いないと思うのですが、vector内ではどのようにデータの処理が行われているのでしょうか
色々試したところ[m+1]なら3つほど実行時エラー、[m*2]なら1つだけ実行時エラーが返ってきました
何度も申し訳ありませんが分かる方いらっしゃいましたらご助言お願いします
回答2件
あなたの回答
tips
プレビュー