Submission #1094138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094138		nguyen31hoang08minh2003	Prosjecni (COCI16_prosjecni)	C++14	120 / 120	1 ms	348 KiB

prosjecni

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

/*

    v[x] + v[y] = 1 + e[x][y] (mod 2) for every x, y

    e[x][y] = 1 if x and y were initially connected

    N               variables
    N * (N - 1) / 2 equations

    -------------------------------------------------

    It can be noticed that
        if (n - 1) following equations are chosen,
            all remaining equations should be able to be determined

            v[1]        + v[n] = 1 + e[1][n]        (mod 2)
            ...
            v[n - 2]    + v[n] = 1 + e[n - 1][n]    (mod 2)

        because
            for every 1 <= x < y < n then
                we have
                    v[x] + v[n] = 1 + e[x][n]
                    v[y] + v[n] = 1 + e[y][n]
                =>  v[x] + v[y] = 1 + e[x][n] + e[y][n]

            this means that,
                as long as all remaining equations are consistent with these (n - 1) chosen equations
                    any solutions of this systems of these (n - 1) equations can be chosen
                        as solutions of the complete system of n * (n - 1) / 2 equations
                            (it is obvious that the system of (n - 1) equations should have solutions;
                             this can be easily proved by substituting one variable and determine remaining variables and check consistency)

*/

constexpr int MAX_N = 102;

int N;
ll result[MAX_N][MAX_N];

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
//    freopen("output.OUT", "w", stdout);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N;

    if (N & 1) {
        int counter = 0;
        fort(x, 1, N) {
            fort(y, 1, N)
                cout << (++counter) << ' ';
            cout << '\n';
        }
        return 0;
    }

    if (N == 2) {
        /*

            The average value is always between two numbers

        */
        cout << -1 << '\n';
        return 0;
    }

    int delta = 0;

    fort(y, 1, N) {
        result[1][y] = y;
        delta += y;
    }

    for (; delta % N; ++delta)
        ++result[1][N];

    /*

        "Ceil" up average value

    */

    delta = (result[1][N] / N + 1) * N;

    fort(y, 1, N) {
        fore(x, 2, N) {
            result[x][y] = result[x - 1][y] + delta;
            result[N][y] += result[x][y];
        }
        result[N][y] = N * result[N - 1][y] - result[N][y] - result[1][y];
    }

    fort(x, 1, N) {
        fort(y, 1, N)
            cout << result[x][y] << ' ';
        cout << '\n';
    }

//    #ifdef LOCAL
//    fort(i, 1, N) {
//        ll row = 0, column = 0;
//        fort(j, 1, N) {
//            row += result[i][j];
//            column += result[j][i];
//        }
//        cerr << "Row " << i << ": " << 1.0 * row / N << '\n'
//             << "Column " << i << ": " << 1.0 * column / N << '\n';
//    }
//    #endif // LOCAL

    return 0;
}

• Subtask 1: 120 / 120