Submission #242655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
242655	2020-06-28T16:10:27 Z	Vimmer	Prosjecni (COCI16_prosjecni)	C++14	120 / 120	7 ms	384 KB

prosjecni

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200101
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;

    cin >> n;

    int a[n][n], u = 1;

    for (int i = 0; i < n - 1; i++)
    {
        set <int> se; se.clear();

        ll sm = 0;

        int mx = 0;

        for (int j = 0; j < n - 1; j++)
        {
            sm += u;

            mx = max(mx, u);

            se.insert(u);

            a[i][j] = u++;
        }

        for (; u <= 10000000; u++)
        {
            if ((sm + u) % n != 0) continue;

            int val = (sm + u) / n;

            if (val > mx) {cout << -1 << endl; exit(0);}

            if (se.find(val) != se.end()) {a[i][n - 1] = u++; break;}
        }
    }

    for (int j = 0; j < n - 1; j++)
    {
        ll sm = 0;

        int mx = 0;

        set <int> se; se.clear();

        for (int i = 0; i < n - 1; i++) {mx = max(mx, a[i][j]); se.insert(a[i][j]); sm += a[i][j];}

        for (; u <= 10000000; u++)
        {
            if ((sm + u) % n != 0) continue;

            int val = (sm + u) / n;

            if (val > mx) {cout << -1 << endl; exit(0);}

            if (se.find(val) != se.end()) {a[n - 1][j] = u++; break;}
        }
    }

    ll sm = 0, smr = 0;

    int mxl = 0, mxr = 0;

    set <int> sl, sr; sl.clear(); sr.clear();

    for (int i = 0; i < n - 1; i++) {sm += a[i][n - 1]; mxl = max(mxl, a[i][n - 1]); sl.insert(a[i][n - 1]); sr.insert(a[n - 1][i]); mxr = max(mxr, a[n - 1][i]); smr += a[n - 1][i];}

    for (; u <= 10000000; u++)
    {
            if ((sm + u) % n != 0) continue;

            if ((smr + u) % n != 0) continue;

            int val = (sm + u) / n;

            if (val > mxl) {cout << -1 << endl; exit(0);}

            val = (smr + u) / n;

            if (val > mxr) {cout << -1 << endl; exit(0);}

            if (sl.find((sm + u) / n) != sl.end() && sr.find(val) != sr.end()) {a[n - 1][n - 1] = u++; break;}
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) cout << a[i][j] << " ";

        cout << endl;
    }
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	6 ms	384 KB	Output is correct
8	Correct	7 ms	384 KB	Output is correct
9	Correct	7 ms	384 KB	Output is correct
10	Correct	7 ms	384 KB	Output is correct