Codeforces #331 Div.2 C

Codeforces331_2C.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define nil -1
#define num 100000
typedef long long ll;

using namespace std;

inline int input(){
    int a;
    cin >> a;
    return a;
}

template <typename T>
inline void output(T a, int p) {
    if(p){
        cout << fixed << setprecision(p)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

// end of template

int main() {
    cin.tie(0);
    // source code
    
    int N = input();
    vector<ll> count(2 * num + 1, 0);
    vector<ll> W(N);
    vector<ll> now(num + 1, -1);
    vector<pair<ll, ll>> ans;
    
    rep(i, N){
        int x, y;
        cin >> x >> y;
        count[y - x + num]++;
    }
    
    rep(i, N){
        int w; // y - x
        cin >> w;
        W[i] = w;
        count[w + num]--;
    }
    
    bool ret = true;
    rep(i, 2 * num + 1){
        if (count[i] != 0) {
            ret = false;
            output("NO", 0);
            return 0;
        }
    }
    
    rep(i, num + 1){
        now[i] = i * (-1);
    }
    
    rep(i, N){
        int l = 0;
        int r = num;
        int cnt = 0;
        while (cnt < 50) {
            int mid = (l + r) / 2;
            if (W[i] > now[mid]) {
                r = mid + 1;
            }
            else{
                l = mid;
            }
            cnt++;
        }
        if (W[i] == now[l]) {
            if (l == 0 || now[l - 1] > now[l]) {
                ans.push_back(make_pair(l, W[i] + l));
                now[l]++;
            }
            else{
                ret = false;
                break;
            }
        }
        else if (W[i + 1] == now[l]) {
            if (l == 0 || now[l - 1] > now[l]) {
                ans.push_back(make_pair(l + 1, W[i] + l + 1));
                now[l]++;
            }
            else{
                ret = false;
                break;
            }
        }
        else{
            ret = false;
            break;
        }
    }
    
    if (ret) {
        output("YES", 0);
        rep(i, ans.size()){
            cout << ans[i].first << " " << ans[i].second << endl;
        }
    }
    else{
        output("NO", 0);
    }
    
    return 0;
}