oj.uz

Submission #880851

# Submission time Handle Problem Language Result Execution time Memory
880851 2023-11-30T07:12:47 Z dimashhh Chessboard (IZhO18_chessboard) C++17
0 / 100
 36 ms 102356 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;

#define int long long
int odd[N][101],even[N][101],it = 0;
ll col_eq(int k,int x,int y,int x1,int y1){
    ll ret = (odd[x1][k] - odd[x - 1][k]) * (odd[y1][k] - odd[y - 1][k]);
    ret += (even[x1][k] - even[x - 1][k]) *1ll* (even[y1][k] - even[y - 1][k]);
    return ret;
}
ll col_non_eq(int k,int x,int y,int x1,int y1){
    ll ret = (odd[x1][k] - odd[x - 1][k]) * (even[y1][k] - even[y - 1][k]);
    ret += (even[x1][k] - even[x - 1][k]) *1ll* (odd[y1][k] - odd[y - 1][k]);
    return ret;
}
vector<pair<pair<int,int>,pair<int,int>>> a;
ll n,k;
int get(ll del,ll i){
    ll res1 = 0,res2 = 0;
    for(auto [x,y]:a){
        res1 += col_eq(i,x.first,x.second,y.first,y.second);
        res2 += col_non_eq(i,x.first,x.second,y.first,y.second);
    }
    res1 = ((n * n / del / del) + 1) / 2 * (del * del) + res2 - res1;
    // cout << ((n * n / del / del) + 1) / 2 * del * del << '\n';
    return min(res1,n * n - res1);
}
void test(){
    cin >> n >> k;
    for(int i = 1;i <= k;i++){
        int x,y,x1,y1;
        cin >> x >> y >> x1 >> y1;
        a.push_back({{x,y},{x1,y1}});
    }
    // ll res = 1e10;
    for(int i = 1;i < n;i++){
        if(n % i == 0){
            for(int j = 1;j <= n;j++){
                int x = (j + i - 1) / i;
                odd[j][it] = odd[j - 1][it];
                even[j][it] = even[j - 1][it];
                if(x & 1){
                    odd[j][it]++;
                }else{
                    even[j][it]++;
                }
            }
            it++;
        }
    }
    // it = 0;
    // for(int i = 1;i < n;i++){
    //     if(n % i == 0){
    //         res = min(res,1ll*get(i,it));
    //         it++;
    //     }
    // }
    cout << get(2,1);
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    test();
}

Compilation message

chessboard.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 102356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 102356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -