[백준 11670] 초등 수학

[ghdcksgml1]

야발! 제목보고 쉬워보여서 깝치다가 3일 동안 못푼 문제 (반례 지옥)

아이디어

이분매칭 문제인데,, 좌표압축, 이분탐색까지 합쳐져서 이분매칭의 원리를 제대로 모른다면 풀 수 없는 문제이다.

시간복잡도

O(VE)

소스코드

// 언어 : C++ , (성공/실패) : 1/12 , 메모리 : 2756 KB , 시간 : 36ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#define MAX 10101

using namespace std;
typedef long long ll;

vector<ll> a[MAX];
bool c[MAX];
ll d[10101];

vector<pair<ll,ll>> v;
vector<ll> y;

bool dfs(ll x){
    for(auto t : a[x]){
        if(c[t]) continue;
        c[t] = true;
        if(d[t]==-1 || dfs(d[t])){
            d[t] = x;
            return true;
        }
    }
    return false;
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll n; cin>>n;
    for(ll i=0;i<n;i++){
        ll tmp1,tmp2; cin>>tmp1>>tmp2;
        v.push_back({tmp1,tmp2});
        ll sum = tmp1 + tmp2;
        ll sub = tmp1 - tmp2;
        ll mul = tmp1 * tmp2;
        y.push_back(sum);
        y.push_back(sub);
        y.push_back(mul);
    }

    sort(y.begin(),y.end());
    y.erase(unique(y.begin(),y.end()),y.end());

    for(ll i=0;i<v.size();i++){
        ll sum = v[i].first + v[i].second;
        ll sub = v[i].first - v[i].second;
        ll mul = v[i].first * v[i].second;
        a[lower_bound(y.begin(), y.end(),sum) - y.begin()].push_back(i);
        a[lower_bound(y.begin(), y.end(),sub) - y.begin()].push_back(i);
        a[lower_bound(y.begin(), y.end(),mul) - y.begin()].push_back(i);
    }

    fill(d,d+MAX,-1);

    ll cnt = 0;
    for(ll i=0;i<y.size();i++){
        fill(c,c+MAX,false);
        if(dfs(i)) cnt++;
    }

    if(cnt != n) cout<<"impossible"<<'\n';
    else{
        for(ll i=0;i<y.size();i++){
            if(d[i] != -1) {
                ll sum = v[i].first + v[i].second;
                ll sub = v[i].first - v[i].second;
                ll mul = v[i].first * v[i].second;
                if (y[d[i]] == sum) {
                    printf("%lld + %lld = %lld\n", v[i].first, v[i].second, y[d[i]]);
                    continue;
                }
                else if (y[d[i]] == sub) {
                    printf("%lld - %lld = %lld\n", v[i].first, v[i].second, y[d[i]]);
                    continue;
                }
                else if (y[d[i]] == mul) {
                    printf("%lld * %lld = %lld\n", v[i].first, v[i].second, y[d[i]]);
                    continue;
                }
            }
        }
    }

    return 0;
}