結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー applejam
提出日時 2026-01-23 23:03:52
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,129 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,988 ms
コンパイル使用メモリ 398,484 KB
実行使用メモリ 20,608 KB
最終ジャッジ日時 2026-01-23 23:04:19
合計ジャッジ時間 26,064 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
using pp = pair<ll, ll>;

void solve(){
    int n, m, k; ll p; cin >> n >> m >> k >> p;
    vll t(n), c(n), b(m), d(m), s(k);
    rep(i, n)cin >> t[i];
    rep(i, n)cin >> c[i];
    rep(i, m)cin >> b[i];
    rep(i, m)cin >> d[i];
    rep(i, k)cin >> s[i];
    /*vector<pair<ll, pp>> vp;
    rep(i, n)rep(j, m){
        ll a = t[i]+b[j];
        if(c[i] == d[j])a -= s[c[i]-1];
        vp.push_back({a, {i, j}});
    }sort(all(vp));
    int j = 0;
    for(auto i : vp){
        j++;
        cout << j << " " << i.first << " : " << i.second.first << "," << i.second.second << endl; 
    }*/
    vector<pp> tp(n), bt(m);
    rep(i, n)tp[i] = {t[i], c[i]};
    rep(i, m)bt[i] = {b[i], d[i]};
    map<pp, int> mp2; rep(i, m)mp2[bt[i]] = i+1;
    sort(all(bt));
   

    vvll same(k);
    rep(i, m){
        same[bt[i].second-1].push_back(bt[i].first);
    }
    vll bc(m); rep(i, m)bc[i] = bt[i].first;
    vvi bk(k); rep(i, m)bk[bt[i].second-1].push_back(i);

    ll l = 0, r = 4e12;
    ll mid;
    unordered_map<ll, pp> mp;
    unordered_map<ll, int> key;
    while(r-l > 1){
        mid = (l+r)/2;
        ll tmp = 0;
        rep(i, n){
            auto [a, e] = tp[i]; e--;
            ll t2 = upper_bound(all(bc), mid-a) - begin(bc);
            if(same[e].size() == 0){
                tmp += t2;
                if(mp.count(mid) == 0){
                    if(t2 > 0 && a + bc[t2-1] == mid){
                        mp[mid] = {i, t2-1};
                        key[mid] = 0;
                    }
                }
                continue;
            }
            ll t3 = upper_bound(all(same[e]), mid-a+s[e]) - begin(same[e]);
            ll t4 = upper_bound(all(same[e]), mid-a) - begin(same[e]);
            tmp += t2+t3-t4;
            if(mp.count(mid) > 0)continue;
            if(t2+t3-t4 == 0)continue;
            if(t3 > 0 && a + same[e][t3-1] - s[e]== mid){
                mp[mid] = {i, t3-1};
                key[mid] = 1;
            }else if(t2 > 0 && a + bc[t2-1] == mid && bt[t2-1].second != e){
                mp[mid] = {i, t2-1};
                key[mid] = 0;
            }
        }
        if(tmp < p){
            l = mid;
        }else{
            r = mid;
        }
    }

    auto [f, g] = mp[r];
    if(key[r] == 0){
        cout << f+1 << " " << mp2[bt[g]] << endl;
    }else{
        int h = tp[f].second-1;
        cout << f+1 << " " << mp2[bt[bk[h][g]]] << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q; cin >> q; 
    while(q--)solve();
    return 0;
}
0