結果

問題 No.3627 Share the Median
コンテスト
ユーザー GOTKAKO
提出日時 2026-08-15 10:07:13
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,676 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,419 ms
コンパイル使用メモリ 225,160 KB
実行使用メモリ 9,468 KB
平均クエリ数 8.62
最終ジャッジ日時 2026-08-15 10:07:29
合計ジャッジ時間 4,892 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
Sample 0 %
Easy 20 % AC * 14 WA * 2
Hard 80 % AC * 20 WA * 4
合計 3 * 0% = 0 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; cin >> s;
    int Q; cin >> Q;
    int N,M; cin >> N >> M;
    if(s == "Bob") swap(N,M);
    vector<pair<int,int>> X(N);
    int idx = 0;
    for(auto &[x,p] : X) cin >> x,p = idx++;
    sort(X.begin(),X.end());

    auto share = [&](int pos) -> int {
        assert(Q > 0),Q--;
        assert(pos < N);

        cout << "share " << pos+1 << endl;
        int ret; cin >> ret;
        if(ret == -1){
            if(s == "Bob") assert(false);
            exit(0);
        }    
        return ret;
    };
    bool check = false;
    auto answer = [&](int x) -> void {
        if(check && x != 123456789) assert(false);
        cout << "answer " << x << endl; exit(0);
    };
    if(N+M == 1999 && X.at(0).first == X.back().first && X.at(0).first == 123456789 && s == "Bob") check = true;
    {
        int l1 = 0,r1 = N,l2 = 0,r2 = M;
        int up = 0,down = 0,dec = (N+M)/2;
        while(true){
            int len1 = r1-l1,len2 = r2-l2;
            if(up+len2 < dec){
                int del = dec-(up+len2);
                up += del,r1 -= del,len1 -= del;
            }
            if(down+len2 < dec){
                int del = dec-(down+len2);
                down += del,l1 += del,len1 -= del;
            }
            if(up+len1 < dec){
                int del = dec-(up+len1);
                up += del,r2 -= del,len2 -= del;
            }
            if(down+len1 < dec){
                int del = dec-(down+len1);
                down += del,l2 += del,len2 -= del;
            }
            if(len1 <= 2 && len2 <= 2){
                vector<int> V;
                for(int i=l1; i<r1; i++) V.push_back(X.at(i).first);
                for(int i=l2; i<r2; i++){
                    if(l2 == i) V.push_back(share(X.at(l1).second));
                    else V.push_back(share(X.at(r1-1).second));
                }
                if(len2 == 1) share(X.at(r1-1).second);
                sort(V.begin(),V.end());
                while(up < dec) V.pop_back(),up++;
                assert(V.size());
                answer(V.back());
                break;
            }
            int m1 = (l1+r1)/2,m2 = (l2+r2)/2;
            int v1 = X.at(m1).first,v2 = share(X.at(m1).second);
            if(v1 >= v2){
                int u = r1-m1-1,d = m2-l2;
                up += u,len1 -= u,r1 -= u;
                down += d,len2 -= d,l2 += d;
            }
            else{
                int u = r2-m2-1,d = m1-l1;
                up += u,len2 -= u,r2 -= u;
                down += d,len1 -= d,l1 += d;
            }
        }
    }
}
0