Cod sursa(job #987885)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 august 2013 17:05:27
Problema Dame Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cassert>

#include <vector>
#include <algorithm>

using namespace std;

vector< pair<int, int> > Queens;
int N;

inline bool ValidArrangement(const vector<int> &primaryDiagonal, const vector<int> &secondaryDiagonal) {
    for (const auto &d: primaryDiagonal)
        if (d > 1)
            return false;
    for (const auto &d: secondaryDiagonal)
        if (d > 1)
            return false;
    return true;
}

void Solve() {
    if (2 <= N && N <= 3) {
        Queens.push_back(make_pair(0, 0));
        if (N == 3)
            Queens.push_back(make_pair(1, 2));
        return;
    }
    srand(time(0));
    vector<int> permutation = vector<int>(N), primaryDiagonal, secondaryDiagonal;
    for (int i = 0; i < N; ++i)
        permutation[i] = i;
    do {
        random_shuffle(permutation.begin(), permutation.end());
        primaryDiagonal = secondaryDiagonal = vector<int>(2 * N, 0);
        for (int i = 0; i < N; ++i) {
            ++primaryDiagonal[i + permutation[i]];
            ++secondaryDiagonal[N + i - permutation[i]];
        }
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                int ii = permutation[i], jj = permutation[j];
                int coefficient = 0;
                coefficient += (primaryDiagonal[i + ii] > 1 ? -1 : 0);
                coefficient += (secondaryDiagonal[N + i - ii] > 1 ? -1 : 0);
                coefficient += (primaryDiagonal[j + jj] > 1 ? -1 : 0);
                coefficient += (secondaryDiagonal[N + j - jj] > 1 ? -1 : 0);
                coefficient += (primaryDiagonal[i + jj] > 0 ? 1 : 0);
                coefficient += (secondaryDiagonal[N - i + jj] > 0 ? 1 : 0);
                coefficient += (primaryDiagonal[j + ii] > 0 ? 1 : 0);
                coefficient += (secondaryDiagonal[N + j - ii] > 0 ? 1 : 0);
                if (coefficient < 0) {
                    --primaryDiagonal[i + ii];
                    --secondaryDiagonal[N + i - ii];
                    --primaryDiagonal[j + jj];
                    --secondaryDiagonal[N + j - jj];
                    swap(permutation[i], permutation[j]);
                    swap(ii, jj);
                    ++primaryDiagonal[i + ii];
                    ++secondaryDiagonal[N + i - ii];
                    ++primaryDiagonal[j + jj];
                    ++secondaryDiagonal[N + j - jj];
                }
            }
        }
    } while (!ValidArrangement(primaryDiagonal, secondaryDiagonal));
    for (int i = 0; i < N; ++i)
        Queens.push_back(make_pair(i, permutation[i]));
}

void Read() {
    assert(freopen("dame.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
}

void Print() {
    assert(freopen("dame.out", "w", stdout));
    printf("%d\n", int(Queens.size()));
    for (const auto &q: Queens)
        printf("%d %d\n", q.first + 1, q.second + 1);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}