結果
| 問題 | No.2114 01 Matching |
| ユーザー |
 kotatsugame
|
| 提出日時 | 2022-10-28 23:17:16 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,426 bytes |
| コンパイル時間 | 2,313 ms |
| コンパイル使用メモリ | 98,248 KB |
| 実行使用メモリ | 11,960 KB |
| 最終ジャッジ日時 | 2023-09-20 06:31:47 |
| 合計ジャッジ時間 | 15,341 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
コンパイルメッセージ
main.cpp:10:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type]
10 | main()
| ^~~~
ソースコード
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
int N,M,K;
map<int,pair<vector<int>,vector<int> > >mp;
main()
{
cin>>N>>M>>K;
for(int i=0;i<N+M;i++)
{
int A;cin>>A;
if(i<N)mp[A%K].first.push_back(A/K);
else mp[A%K].second.push_back(A/K);
}
long ans=0;
for(auto it=mp.begin();it!=mp.end();it++)
{
vector<int>B,R;
B.swap(it->second.first);
R.swap(it->second.second);
if(N>M)B.swap(R);
if(B.size()>R.size()||N==M&&B.size()!=R.size())
{
cout<<-1<<endl;
return 0;
}
sort(B.begin(),B.end());
priority_queue<int>LQ;
multiset<pair<int,int> >RS,RSS;
for(int r:R)
{
RS.insert(make_pair(r,0));
RSS.insert(make_pair(r+0,0));
}
for(int b:B)
{
while(!RS.empty()&&RS.begin()->first<=b)
{
pair<int,int>p=*RS.begin();
RS.erase(RS.begin());
RSS.erase(RSS.find(make_pair(p.first+p.second,p.second)));
LQ.push(p.first-p.second);
}
long l=1e15,r=1e15;
if(!LQ.empty())l=b-LQ.top();
if(!RSS.empty())r=RSS.begin()->first-b;
if(l<=r)
{
ans+=l;
LQ.pop();
}
else
{
ans+=r;
pair<int,int>p=*RSS.begin();
RSS.erase(RSS.begin());
RS.erase(RSS.find(make_pair(p.first-p.second,p.second)));
if(l<(long)1e15)
{
RS.insert(make_pair(p.first-p.second,l-r));
RSS.insert(make_pair(p.first-p.second+l-r,l-r));
}
}
}
}
cout<<ans<<endl;
}