Cod sursa(job #231726)

Utilizator goguGogu Marian gogu Data 14 decembrie 2008 12:52:30
Problema Tablete Scor 100
Compilator cpp Status done
Runda Algoritmiada 2009, Runda 1, Clasele 9-10 Marime 1.68 kb
#include <cstdio>
#include <bitset>
#include <vector>
#include <algorithm>

using namespace std;

int n, k;
int sol[1020][1020];
bitset<(1<<20)> mark;

void check(){
     bitset<(1<<20)> bun;
     bool ok = true;
     for (int i=0; i<n; i++)
         if (sol[i][k]%2) ok = false;
     for (int i=0; i<n; i++)
         for (int j=1; j<n; j++)
             if (sol[i][j-1] > sol[i][j]) ok = false;
     for (int i=0; i<n; i++)
         for (int j=0; j<n; j++){
             if (bun[sol[i][j]]) ok = false;
             if (sol[i][j] < 1 || sol[i][j] > n*n) ok = false;
             bun[sol[i][j]] = true;
         }
     if (!ok) printf("Nu e bine!\n");
}

void rezolva(){
     int N = n*n;
     for (int i=n-1; i>=0; i--)
         for (int j=n-1; j>k; j--)
             if ((i != 0) || (j != k+1)){
                mark[N] = true;
                sol[i][j] = N--;
             }
     int last;
     if (N%2 == 0){
        sol[0][k+1] = N-1;
        last = N;
     }  else   {
        sol[0][k+1] = N;
        last = N-1;
     }
     mark[sol[0][k+1]] = true;
     for (int i=n-1; i>=0; i--){
         mark[last] = true;         
         sol[i][k] = last;
         last -= 2;
     }
     for (int i=n-1; i>=0; i--)
         for (int j=k-1; j>=0; j--){
             while (mark[N])
                   N--;
             sol[i][j] = N;
             mark[N] = true;
         }
}

int main(){
    freopen("tablete.in", "r", stdin);
    freopen("tablete.out", "w", stdout);
    scanf("%d %d", &n, &k);
    k--;
    rezolva();
    check();
    for (int i=0; i<n; i++, printf("\n"))
        for (int j=0; j<n; j++)
            printf("%d ", sol[i][j]);
}