Showstopper POJ3484

投稿日：2022/12/21 更新日:2022/12/21

POJ

競プロ

問題：http://poj.org/problem?id=3484

問題

正整数 $X_i, Y_i, Z_i$ が与えられます。初項 $X_i$ 、公差 $Z_i$ 、末項 $Y_i$ 以下の等差数列を考えます。

整数の出現回数を数えた時、全て偶数回もしくは、1つだけ奇数回です。奇数回出現しているものがあればその数と出現回数を、そうでなければno corruptionと出力してください。

解法

二分探索を用います。

$M$ 以下の数が何回出現しているかで探索します。もし、奇数回出現する数が $M$ 以下に存在すれば、 $M$ 以下の数の出現回数は奇数回となり、 $M$ 以下に答えが存在すると言えます。そうでなければ、 $M$ 以上に答えが存在すると言えます。

実装

入力が少し大変。

okはok以下の数の出現回数は偶数であるとしてます。

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

void solve(vector<long long>& x, vector<long long>& y, vector<long long>& z){
    int n = x.size();
    if(n == 0)return;

    const long long INF = 1e10 + 100;
    long long ok = 0, ng = INF;
    while(ng - ok > 1){
        long long mid = (ok + ng)/2;

        long long count = 0;
        for(int i = 0;i < n; ++i){
            long long limit = min(mid, y[i]);
            if(limit < x[i])continue;
            count += (limit - x[i])/z[i] + 1;
        }

        if(count%2){
            ng = mid;
        }else{
            ok = mid;
        }
    }

    if(ng == INF){
        printf("no corruption\n");
        return;
    }

    int count = 0;
    for(int i = 0;i < n; ++i){
        if(x[i] <= ng && ng <= y[i] && (ng - x[i])%z[i] == 0){
            count++;
        }
    }

    printf("%lld %d\n", ng, count);
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);

    string s;
    vector<long long> x, y, z;
    while(getline(cin, s)){
        if(s.size() != 0){
            long long vx, vy, vz;
            istringstream iss(s);
            iss >> vx >> vy >> vz;
            x.push_back(vx);
            y.push_back(vy);
            z.push_back(vz);
        }else{
            solve(x, y, z);
            x.clear();
            y.clear();
            z.clear();
        }
    }
    solve(x, y, z);
    return 0;
}