oj.uz

Submission #167769

# Submission time Handle Problem Language Result Execution time Memory
167769 2019-12-10T05:45:30 Z Toirov_Sadi Chessboard (IZhO18_chessboard) C++17
23 / 100
 20 ms 2936 KB 
#include <bits/stdc++.h>

#define fr first
#define se second

using namespace std;

const long long N = 1e3 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int k;
int q[N];
int w[N];
int e[N];
int r[N];
int a[N][N];
int res = inf;
int go(int i, int j, int x, int y){
    if(i > n || j > n || i <= 0 || j <= 0){
        return 0;
    }
    int cnt = 0;
    for(int k = i; k < i + x; k ++){
        for(int h = j; h < j + x; h ++){
            cnt += (a[k][h] == y);
        }
    }return cnt;
}
void can(int x){
    int cnt = 0;
    int ans = 0, ans2 = 0;
    for(int i = 1; i <= n; i += x){
        for(int j = (cnt % 2 ? 0 : x) + 1; j <= n; j += 2 * x){
            ans += go(i, j, x, 0);
            ans += go(i, j + x * (cnt % 2 ? 1 : -1), x, 1);
            if(cnt % 2 == 0 && (j + 2 * x - 1) == n){
                ans += go(i, j + x, x, 1);
            }
        }
        for(int j = (cnt % 2 ? x : 0) + 1; j <= n; j += 2 * x){
            ans2 += go(i, j, x, 0);
            ans2 += go(i, j + x * (cnt % 2 ? -1 : 1), x, 1);
            if(cnt % 2 && (j + 2 * x - 1) == n){
                ans2 += go(i, j + x, x, 1);
            }
        }cnt ++;
    }res = min({res, ans, ans2});
}
int main()
{
    /// freopen("input.txt", "r", stdin);
    /// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio( false );

    cin >> n >> k;
    for(int i = 1; i <= k; i ++){
        cin >> q[i] >> w[i] >> e[i] >> r[i];
        for(int j = q[i]; j <= e[i]; j ++){
            for(int k = w[i]; k <= r[i]; k ++){
                a[j][k] = 1;
            }
        }
    }
    for(int i = 1; i * i <= n; i ++){
        if(n % i == 0){
            can(i);
            if(n / i != i && (n / i) < n){
                can(n / i);
            }
        }
    }cout << res << "\n";
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 3 ms 632 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 3 ms 632 KB Output is correct
16 Incorrect 20 ms 2936 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -