提出 #76550020

---

ソースコード 拡げる

#ifdef CPTEST
#include "D.h"
#endif
#include <atcoder/all>
#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
//競プロ用横着定義
using namespace std;
typedef long long ll;
typedef vector<ll> intVec;
typedef vector<string> strVec;
#define rep(i, l, r) for (ll i = l; i < (ll)(r); i++)
string str(ll v)
{
    return to_string(v);
}
ll num(string s)
{
    return strtoll(s.c_str(), nullptr, 10);
}

bool isDebugPrintOn = true;

//ユーティリティ
//1行読み取り
string readLine(istream& in)
{
    string buf;
    getline(in, buf);
    return buf;
}
ll num(istream &in)
{
    return num(readLine(in));
}

//文字列結合
string Join(intVec iv, string separator)
{
    string buf;
    for(ll i:iv)
    {
        buf += str(i) + separator;
    }
    buf.erase(buf.size() - separator.size(), separator.size());
    return buf;
}
string Join(strVec sv, string separator)
{
    string buf;
    for(string s:sv)
    {
        buf += s + separator;
    }
    buf.erase(buf.size() - separator.size(), separator.size());
    return buf;
}

//文字列をスペース区切りでintの配列に分解
intVec innerSplitI(const string& org, ll size = -1)
{
    intVec dst;
    if(size > 0)
    {
        dst.reserve(size);
    }
    ll ofs = 0;
    size_t sp = 0;
    const char* cstr = org.c_str();
    do
    {
        sp = org.find_first_of(' ', ofs);
        dst.push_back(strtoll(&cstr[ofs], nullptr, 10));
        ofs = sp + 1;
    } while(sp != string::npos);
    return dst;
}
intVec splitI(istream& in, ll size = -1)
{
    return innerSplitI(readLine(in), size);
}

//文字列をスペース区切りでstringに分解
void innerSplitS(const string& org, strVec& dst)
{
    ll ofs = 0;
    size_t sp = 0;
    do
    {
        sp = org.find_first_of(' ', ofs);
        dst.push_back(org.substr(ofs, sp - ofs));
        ofs = sp + 1;
    } while(sp != string::npos);
}
void splitS(istream& in, strVec& dst)
{
    innerSplitS(readLine(in), dst);
}

//テスト実行用デバッグ出力
void DebugPrint(const string& str)
{
    if(isDebugPrintOn)
    {
        cout << str << endl;
    }
}
void DebugPrint(const ll val)
{
    if(isDebugPrintOn)
    {
        cout << to_string(val) << endl;
    }
}
void DebugPrint(const intVec& iv)
{
    if(isDebugPrintOn)
    {
        string buf;
        buf = "[";
        buf += Join(iv, ", ");
        buf += "]";
        cout << buf << endl;
    }
}
void DebugPrint(const strVec& sv)
{
    if(isDebugPrintOn)
    {
        string buf;
        buf = "[";
        buf += Join(sv, ", ");
        buf += "]";
        cout << buf << endl;
    }
}

string Impl_D(istream& inputs)
{
    // show me your moves!
    // 最初のピースは絶対にw=Wかh=H
    // WとHの両方でソートしたリストを持ち、
    // 最大のものを一つ除去。
    // 最大が使用済みなら次に繰り上げ。
    // 使用済みかはset
    
    intVec iv = splitI(inputs);
    ll H = iv[0];
    ll W = iv[1];
    ll N = iv[2];
    vector<tuple<ll, ll, ll>> pieceH;
    vector<tuple<ll, ll, ll>> pieceW;
    ll restH = H;
    ll restW = W;
    rep(i, 0, N)
    {
        iv = splitI(inputs);
        ll h = iv[0];
        ll w = iv[1];
        pieceH.push_back(make_tuple(h, w, i));
        pieceW.push_back(make_tuple(w, h, i));
    }
    vector<pair<ll, ll>> ansP;
    ansP.resize(N);
    set<ll> used;
    sort(pieceH.begin(), pieceH.end());
    sort(pieceW.begin(), pieceW.end());
    ll curH = N - 1;
    ll curW = N - 1;
    rep(i, 0, N)
    {
        while(true)
        {
            if(get<0>(pieceH[curH]) == restH)
            {
                if(used.find(get<2>(pieceH[curH])) == used.end())
                {
                    ansP[get<2>(pieceH[curH])].first = (H - restH) + 1;
                    ansP[get<2>(pieceH[curH])].second = (W - restW) + 1;
                    restW -= get<1>(pieceH[curH]);
                    used.insert(get<2>(pieceH[curH]));
                    curH--;
                    break;
                }
                else
                {
                    curH--;
                }
            }
            else if(get<0>(pieceW[curW]) == restW)
            {
                if(used.find(get<2>(pieceW[curW])) == used.end())
                {
                    ansP[get<2>(pieceW[curW])].first = (H - restH) + 1;
                    ansP[get<2>(pieceW[curW])].second = (W - restW) + 1;
                    restH -= get<1>(pieceW[curW]);
                    used.insert(get<2>(pieceW[curW]));
                    curW--;
                    break;
                }
                else
                {
                    curW--;
                }
            }
        }
    }

    string ans;
    rep(i, 0, N)
    {
        ans += str(ansP[i].first) + " " + str(ansP[i].second) + "\n";
    }
    return ans;
}

#ifndef CPTEST
int main(int, char**)
{
    isDebugPrintOn = false;
    cout << Impl_D(cin);
}
#endif

提出情報

ジャッジ結果