Submission #44993974

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using db = long double;
using P = pair<int, int>;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<std::vector<T>> &r){
    if(r.size() == 0){
        out << "||";
        return out;
    }
    for(const auto&v : r) out << v << endl;
    out << endl;
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &r){
    if(r.size() == 0){
        out << "[]";
        return out;
    }
    out << "[";
    for(int i{}; i < (int)r.size() - 1; ++i) out << r[i] << ",";
    out << r.back() << "]";
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::set<T> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << *it << ",";
    out << *e << "}";
    return out;
}

template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::map<T, U> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << it -> first << ":" << it -> second << ",";
    out << e -> first << ":" << e -> second << "}";
    return out;
}
 
template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &r){
    out << "(" << r.first << "," << r.second << ")";
    return out;
}

mt19937 engine;

void solve(){
    int d, n;
    cin >> d >> n;
    auto ok = [&](int x, int y){
        return 0 <= x and x < d and 0 <= y and y < d;
    };
    int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    auto con = vector(d, vector(d, -1));
    constexpr P df(-1, -1), er(-2, -2);
    auto tr = vector(d, vector(d, df));
    for (int i = 0, x, y; i < n; i++)
    {
        cin >> x >> y;
        con[x][y] = -2;
        tr[x][y] = er;
    }
    int mid = (d-1) / 2;
    tr[0][mid] = er;

    auto cp = [&](int num){
        vector<P> ret;
        for (int p = 0; p < d; p++)
        {
            for (int q = 0; q < d; q++)
            {
                if(con[p][q] != -1) continue;
                con[p][q] = -2;
                vector<P> que;
                que.emplace_back(0, mid);
                auto use = vector(d, vector(d, false));
                use[0][mid] = true;
                int cnt = 0;
                while(not que.empty())
                {
                    auto [x, y] = que.back();
                    que.pop_back();
                    ++cnt;
                    for (int idx = 0; idx < 4; idx++)
                    {
                        int nx = x + dx[idx];
                        int ny = y + dy[idx];
                        if(not ok(nx, ny)) continue;
                        if(con[nx][ny] != -1) continue;
                        if(use[nx][ny]) continue;
                        use[nx][ny] = true;
                        que.emplace_back(nx, ny);
                    }
                }
                con[p][q] = -1;
                if(num == cnt) ret.emplace_back(p, q);
            };
        }
        return ret;
    };

    auto dis = [mid](P l){
        return l.first + abs(l.second - mid);
    };


    for (int cnt = d * d - 1 - n, t; cnt > 0; --cnt)
    {
        cin >> t;
        int tk = t/d + 3;
        auto vcp = cp(cnt);
        sort(begin(vcp), end(vcp), [&](P l, P r){
            return abs(tk-dis(l)) < abs(tk-dis(r));
        });
        /*if(t == 0)
        {
            cerr << t << " " << cnt << endl;
            cerr << vcp << endl;
        }*/
        auto [x, y] = vcp[0];
        cout << x << " " << y << endl;
        con[x][y] = t;
        auto[px, py] = tr[x][y];
    }
    /*
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            cerr << con[i][j] << " ";
        }
        cer r<< endl;
    }cerr << endl;
    */

    for (int i = 0; i < d * d - 1 - n; i++)
    {
        int ans = INT_MAX;
        P cor = df;
        queue<P> q;
        q.emplace(0, mid);
        auto use = vector(d, vector(d, false));
        use[0][mid] = true;
        while(not q.empty())
        {
            auto [x, y] = q.front();
            q.pop();
            //cerr << "!" << x << " " << y << endl;
            for (int idx = 0; idx < 4; idx++)
            {
                int nx = x + dx[idx];
                int ny = y + dy[idx];
            //cerr << "!@" << nx << " " << ny << endl;
                if(not ok(nx, ny)) continue;
                if(use[nx][ny]) continue;
                if(con[nx][ny] == -2) continue;
            //cerr << "!@@" << nx << " " << ny << endl;
                use[nx][ny] = true;
                if(con[nx][ny] >= 0)
                {
                    if(chmin(ans, con[nx][ny]))
                    {
                        cor = P(nx, ny);
                    }
                    continue;
                }
            //cerr << "!@@@" << nx << " " << ny << endl;
                q.emplace(nx, ny);
            }
        }
        auto[x, y] = cor;
        cout << x << " " << y << endl;
        con[x][y] = -1;
    }
    
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    engine = mt19937{42};
    solve();
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:144:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  144 |         auto[px, py] = tr[x][y];
      |             ^~~~~~~~

Judge Result