Submission #954574

#	Time	Username	Problem	Language	Result	Execution time	Memory
954574		Iwantbemaster	Chessboard (IZhO18_chessboard)	C++17	0 / 100	117 ms	262144 KiB

chessboard

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ff first
#define ss second
#pragma GCC optimize("Ofast","inline","-ffast-math")
signed main(){
    int n, m, mn = 1e18; cin >> n >> m;
    int rev = n * n;
    vector<vector<int>> v(n, vector<int>(n, 0));
    while(m--){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;
        for(int i = x1; i <= x2; i++){
            for(int j = y1; j <= y2; j++) v[i][j] = 1;
        }
    } int cnt1 = 0, cnt2 = 0;
    vector<vector<int>> res1(n, vector<int>(n, 0));
    vector<vector<int>> res2;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(n % 2 == 0){
                if((j + (i * (n - 1))) % 2 == 0) res1[i][j] = 0;
                else res1[i][j] = 1;
            } else {
                if((j + (i * n)) % 2 == 0) res1[i][j] = 0;
                else res1[i][j] = 1;
            }
        }
    } for(int i = 0; i < n; i++){
        vector<int> answer_;
        for(int j = 0; j < n; j++){
            answer_.emplace_back(res1[i][j]);
        } res2.emplace_back(answer_);
    } reverse(res2.begin(), res2.end());
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(res1[i][j] != v[i][j]) cnt1++;
            //cout << res1[i][j] << " ";
        }
        //cout << "\n";
    } //cout << "\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(res2[i][j] != v[i][j]) cnt2++;
            //cout << res2[i][j] << " ";
        }
        //cout << "\n";
    } //cout << "\n";
    mn = min(mn, cnt1);
    mn = min(mn, cnt2);
    //cout << cnt1 << " " << cnt2 << "\n";
    vector<vector<int>> qwer;
    //cout << cnt1 << " " << cnt2 << "\n";
    for(int k = 2; k <= n - 1; k++){
        vector<vector<int>> res(n, vector<int>(n, 0));
        int cnt = 0;
        if(n % k == 0){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(i % k == 0 && j % k == 0){
                        cnt++;
                            if(cnt % 2 == 0){
                                for(int q = i; q < i + k; q++){
                                    for(int w = j; w < j + k; w++){
                                        res[q][w] = 1;
                                    }
                                }
                            }
                    }
                }
            } int cur = 0;
            vector<vector<int>> ans(n, vector<int>(n, 0));
            for(int i = k; i < n; i++){
                if((i + 1) % k == 0){
                    cur++;
                    if(cur % 2 != 0){
                        for(int q = i - (k - 1); q <= i; q++){
                            for(int j = 0; j < n; j++){
                                ans[q][j] = res[q][j];
                                res[q][j] = 0;
                            }
                        }
                    }
                }
            } vector<vector<int>> curr;
            for(int i = 0; i < n; i++){
                vector<int> result;
                for(int j = n - 1; j >= 0; j--){
                    result.emplace_back(ans[i][j]);
                } curr.emplace_back(result);
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(res[i][j] == 1){
                        curr[i][j] = 1;
                    } 
                } //cout << "\n";
            } //cout << "\n";
            // if((n * n) % k == 0 && k == wer - 3){
            //     for(int i = 0; i < n; i++){
            //         vector<int> ert;
            //         for(int j = 0; j < n; j++){
            //             ert.emplace_back(curr[i][j]);
            //         } qwer.emplace_back(ert);
            //     }
            // }
            vector<vector<int>> cur_;
            for(int i = 0; i < n; i++){
                vector<int> rty;
                for(int j = 0; j < n; j++){
                    rty.emplace_back(curr[i][j]);
                } cur_.emplace_back(rty);
            }
            int count1 = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(v[i][j] != curr[i][j]){
                        count1++;
                    }
                }
            }
            reverse(curr.begin(), curr.end());
            int sovpadenie_A = 0;
            // for(int i = 0; i < n; i++){
            //     for(int j = 0; j < n; j++){
            //         cout << cur_[i][j] << " ";
            //     } cout << "\n";
            // } cout << "\n";
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(cur_[i][j] == curr[i][j]){
                        sovpadenie_A++;
                    }
                    //cout << curr[i][j] << " ";
                } //cout << "\n";
            } //cout << "\n";
            if(sovpadenie_A == rev){
                for(int i = 0; i < n; i++){
                    vector<int> pkl;
                    for(int j = 0; j < n; j++){
                        pkl.emplace_back(curr[i][j]);
                    } qwer.emplace_back(pkl);
                }
            } else {
                int count2 = 0;
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < n; j++){
                        if(v[i][j] != curr[i][j]){
                            count2++;
                        }
                    }
                } mn = min(count1, mn);
                mn = min(mn, count2);
            }
        }
    } //cout << mn << "\n";
    if(n % 3 == 0){
        vector<vector<int>> asd(n, vector<int> (n));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(qwer[i][j] == 1){
                    asd[i][j] = 0;
                } else if(qwer[i][j] == 0){
                    asd[i][j] = 1;
                }
            }
        } int count__ = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(v[i][j] != asd[i][j]) count__++;
            }
        } mn = min(mn, count__);
    }
    cout << mn;
}
const int fastIO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    return 0;
}();

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30