Cod sursa(job #987891)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 august 2013 17:09:04
Problema Dame Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cassert>

#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1000;

vector< pair<int, int> > Queens;
int N, Permutation[MAX_N], PrimaryDiagonal[2 * MAX_N], SecondaryDiagonal[2 * MAX_N];

inline bool ValidArrangement() {
    for (int i = 0; i < 2 * N; ++i)
        if (PrimaryDiagonal[i] > 1 || SecondaryDiagonal[i] > 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));
    for (int i = 0; i < N; ++i)
        Permutation[i] = i;
    do {
        random_shuffle(Permutation, Permutation + N);
        memset(PrimaryDiagonal, 0, sizeof(PrimaryDiagonal));
        memset(SecondaryDiagonal, 0, sizeof(SecondaryDiagonal));
        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], 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());
    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;
}