oj.uz

Submission #457869

# Submission time Handle Problem Language Result Execution time Memory
457869 2021-08-07T13:04:55 Z Aldas25 Coins (LMIO19_monetos) C++14
21.3603 / 100
 22 ms 1044 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1000100, MAXK = 60;
//const ll MOD = 998244353;
const ll MOD = 1e9+7;
const ll INF = 1e17;

int t, n, k1, k2;

bool grid[310][310], cur[310][310], ans[310][310];
int mn = 310*310;

void printCur () {
    cout << " printing cur" << "\n";
    FOR(i, 0, n-1){
        FOR(j, 0, n-1) cout << cur[i][j] << " ";
        cout << "\n";
    }
    cout << endl;
}

void eval () {
    int cr = 0;
    FOR(i, 0, n-1) FOR(j, 0, n-1) cr += (!grid[i][j] && cur[i][j]);
    if (cr < mn) {
        mn = cr;
        FOR(i, 0, n-1) FOR(j, 0, n-1) ans[i][j] = cur[i][j];
    }

    //cout << " evaled cur, cr = " << cr << endl;
    //printCur();
}

void sol1 () {
    FOR(i, 0, n-1) FOR(j, 0, n-1) {
        if (i < (n/2)) cur[i][j] = false;
        else cur[i][j] = true;
    }
    eval();
}

void sol2 () {
    FOR(i, 0, n-1) FOR(j, 0, n-1) {
        if (j < (n/2)) cur[i][j] = false;
        else cur[i][j] = true;
    }
    eval();
}


void sol3 () {
    FOR(i, 0, n-1) FOR(j, 0, n-1) {
        if (j < (n-i)) cur[i][j] = false;
        else cur[i][j] = true;
    }
    FOR(i, 0, (n/2)-1) {
        cur[i][n-i-1] = true;
    }
    eval();
}

void sol4 () {
    FOR(i, 0, n-1) FOR(j, 0, n-1) {
        if (j < (n-i)) cur[i][j] = false;
        else cur[i][j] = true;
    }
    FOR(i, (n/2), n-1) {
        cur[i][n-i-1] = true;
    }
    eval();
}

void sol5 () {
    FOR(i, 0, n-1) FOR(j, 0, n-1) {
        if (j < (n-i)) cur[i][j] = false;
        else cur[i][j] = true;
    }
    FOR(i, 0, n-1) {
        if (i%2 == 0) cur[i][n-i-1] = true;
    }
    eval();
}

int cnt[310];

void sol6() {

    /// krenta zemyn
    FOR(i, 0, n-1) cnt[i] = 0;
    FOR(i, 0, n-1) FOR(j, 0, n-1) cnt[j] += grid[i][j];


    FOR(i, 0, n-1) FOR(j, 0, n-1) cur[i][j] = false;
    FOR(j, 0, n-1) for (int i = n-1, tmp = 0; tmp < cnt[j]; tmp++, i--) {
        cur[i][j] = true;
    }

    /// krenta desinen
    FOR(i, 0, n-1) cnt[i] = 0;
    FOR(i, 0, n-1) FOR(j, 0, n-1) cnt[i] += cur[i][j];


    FOR(i, 0, n-1) FOR(j, 0, n-1) cur[i][j] = false;
    FOR(i, 0, n-1) for (int j = n-1, tmp = 0; tmp < cnt[i]; tmp++, j--) {
        cur[i][j] = true;
    }

    eval();
}


void sol7() {

    /// krenta desinen
    FOR(i, 0, n-1) cnt[i] = 0;
    FOR(i, 0, n-1) FOR(j, 0, n-1) cnt[i] += grid[i][j];


    FOR(i, 0, n-1) FOR(j, 0, n-1) cur[i][j] = false;
    FOR(i, 0, n-1) for (int j = n-1, tmp = 0; tmp < cnt[i]; tmp++, j--) {
        cur[i][j] = true;
    }

    /// krenta zemyn
    FOR(i, 0, n-1) cnt[i] = 0;
    FOR(i, 0, n-1) FOR(j, 0, n-1) cnt[j] += cur[i][j];


    FOR(i, 0, n-1) FOR(j, 0, n-1) cur[i][j] = false;
    FOR(j, 0, n-1) for (int i = n-1, tmp = 0; tmp < cnt[j]; tmp++, i--) {
        cur[i][j] = true;
    }

    eval();
}

int main()
{
    FAST_IO;

    cin >> t >> n >> k1 >> k2;

    FOR(i, 0, n-1) FOR(j, 0, n-1) cin >> grid[i][j];

    sol1();
    sol2();
    sol3();
    sol4();
    sol5();
    sol6();
    sol7();

    FOR(i, 0, n-1) {
        FOR(j, 0, n-1) cout << ans[i][j] << " ";
        cout << "\n";
    }

    return 0;
}

Subtask #1
21.3602636531 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB K = 22
2 Incorrect 1 ms 332 KB K = 620
3 Partially correct 22 ms 1044 KB K = 19883
4 Partially correct 20 ms 960 KB K = 22856
5 Partially correct 20 ms 828 KB K = 18397
6 Partially correct 20 ms 920 KB K = 22048
7 Partially correct 19 ms 844 KB K = 22245
8 Partially correct 18 ms 912 KB K = 20045
9 Partially correct 19 ms 884 KB K = 21031
10 Partially correct 20 ms 892 KB K = 22112