Qual. D small (WA解)

D-small-wa.cc

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#include "cout11.h"   // oops.消し忘れ
#define NDEBUG
#include <cassert>

typedef pair<int, int> ii;


int render(int N, vector<char>& F, vector<vector<char> >& G) {
    int score = 0;
    vector<pair<char, ii> > Q;

    rep(r, N) rep(c, N) {
        switch (G[r][c]) {
            case '+': case 'x':
                ++score; break;
            case 'o':
                score += 2; break;
        }

        if (r == 0 && G[r][c] == F[c]) continue;
        if (G[r][c] != '.') {
            Q.push_back(make_pair(G[r][c], ii(r, c)));
        }
    }

    bool is_valid = true;
    {
        rep(r, N) rep(c, N) {
            if (G[r][c] == 'o' || G[r][c] == 'x') {

                rep(ri, N) {
                    if (ri == r) continue;
                    if (G[ri][c] == 'o' || G[ri][c] == 'x') { is_valid = false; goto valid_check_end; }
                }

                rep(ci, N) {
                    if (ci == c) continue;
                    if (G[r][ci] == 'o' || G[r][ci] == 'x') { is_valid = false; goto valid_check_end; }
                }
            }
            if (G[r][c] == 'o' || G[r][c] == '+') {

                rep(ci, N) {
                    int d = ci - c;
                    if (d == 0) continue;
                    int ri = r + d;
                    if (0 <= ri && ri < N) {
                        if (G[ri][ci] == 'o' || G[ri][ci] == '+') { is_valid = false; goto valid_check_end; }
                    }
                    ri = r - d;
                    if (0 <= ri && ri < N) {
                        if (G[ri][ci] == 'o' || G[ri][ci] == '+') { is_valid = false; goto valid_check_end; }
                    }
                }
            }
        }
    valid_check_end:
        ;
#ifdef DEBUG
        if (!is_valid) {
            cout << string(all(F)) << endl;
            printf("---- %d\n", is_valid);
            rep(r, N) {
                rep(c, N) {
                    putchar(G[r][c]);
                }
                putchar('\n');
            }
            printf("----\n");
        }
#endif
    }

    printf("%d %lu\n", score, Q.size());
    rep(i, Q.size()) {
        printf("%c %d %d\n", Q[i].first, 1+Q[i].second.first, 1+Q[i].second.second);
    }
    return is_valid;
}

int solve_s(int N, vector<pair<char, ii> >& P) {
    int M = P.size();
    vector<char> F(N, '.');


    int ox_at = -1;
    rep(i, M) {
        char ch = P[i].first;
        int r = P[i].second.first, c = P[i].second.second;
        assert(r == 0);
        F[c] = ch;
        if (ch == 'x' || ch == 'o') ox_at = c;
    }

    vector<vector<char> > G(N, vector<char>(N, '.'));
    G[0].assign(all(F));
    int last = N-1;

    if (ox_at == -1 || G[0][0] == 'o' || G[0][0] == 'x') {
        ox_at = 0;
        G[0][0] = 'o';
        for (int c=1; c<=last; ++c) G[0][c] = '+';
        for (int c=1; c<last; ++c) G[N-1][c] = '+';
        for (int d=1; d<=last; ++d) G[d][d] = 'x';
        return render(N, F, G);
    }
    if (G[0][last] == 'o' || G[0][last] == 'x') {
        for (int c=0; c<last; ++c) G[0][c] = '+';
        for (int c=1; c<last; ++c) G[last][c] = '+';
        for (int d=1; d<=last; ++d) G[d][last-d] = 'x';
        return render(N, F, G);
    }
    else if (F[ox_at] == 'o') {
        for (int c=0; c<N; ++c) {
            if (F[c] == '.') G[0][c] = '+';
        }
        vector<bool> used(N, false);
        used[ox_at] = true;

        G[last][0] = 'x';
        for (int c=1; c<last; ++c) G[last][c] = '+';
        used[0] = true;


        for (int r=1; r<last; ++r) {
            rep(c, N) {
                if (used[c]) continue;
                G[r][c] = 'x'; used[c] = true; break;
            }
        }
        return render(N, F, G);
    } else {

        for (int c=1; c<last; ++c) {
            if (F[c] == '.' || F[c] == '+') {
                G[0][c] = G[last-0][last-c] = '+';
            } else if (F[c] == 'x') {
                G[c][0] = G[last-c][last-0] = '+';
            }
        }
        vector<bool> used(N, false);
        used[ox_at] = true;

        if (G[0][0] == '.') {
            G[last][last] = 'o';
            used[last] = true;
        }
        else if (G[0][last] == '.') {
            G[last][0] = 'o';
            used[0] = true;
        }

        {
            int r = ox_at;
            for (int c=1; c<last; ++c) {
                if (used[c]) continue;
                G[r][c] = 'x'; used[c] = true; break;
            }
            r = last - ox_at;
            if (r != ox_at) {
                for (int c=1; c<last; ++c) {
                    if (used[c]) continue;
                    G[r][c] = 'x'; used[c] = true; break;
                }
            }
        }


        for (int r=1; r<last; ++r) {
            if (r == ox_at || r == last-ox_at) continue;
            rep(c, N) {
                if (used[c]) continue;
                G[r][c] = 'x'; used[c] = true; break;
            }
        }
        return render(N, F, G);
    }

    return false;
}

int main(){
    int _T; cin>>_T;
    rep(_t,_T){
        cout << "Case #" << (1+_t) << ": ";

        int N; cin >> N;
        assert(1 <= N && N <= 100);

        vector<pair<char, ii> > P;
        int M; cin >> M;
        assert(0 <= M && M <= N*N);

        rep(m, M) {
            char ch; int r, c; cin >> ch >> r >> c;
            assert(ch == '+' || ch == 'x' || ch == 'o');
            --r; --c;
            assert(0 <= r && r < N);
            assert(0 <= c && c < N);

            P.push_back(make_pair(ch, ii(r, c)));
        }
        solve_s(N, P);
    }
}