Submission #85332

#	Time	Username	Problem	Language	Result	Execution time	Memory
85332		mra2322001	Chessboard (IZhO18_chessboard)	C++14	8 / 100	51 ms	7424 KiB

chessboard

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, k, f[N][2];
pair <int, int> a[N];
vector <vector <int> > v;

int mau(int x, int id){
    int col = x%2;
    if(col==0 && id==0) col = 1;
    else if(col==1){
        col = id;
    }
    return col;
}

int solve2(vector <pair <int, int> > cur, int sz, int id){
    int Sz = cur.size();
    int res = 0;
    for(int i = 0; i < Sz - 1; i++){
        auto t = cur[i + 1];
        auto t2 = cur[i];
        int x = cur[i + 1].first - cur[i].first;
        if(x==1){
            if(i==Sz - 2) break;
            if(cur[i + 1].first > (n/sz)) continue;
            int col = mau(cur[i + 1].first, id);
            if(col==1) res = res + sz*sz - cur[i + 1].second;
            else res = res + cur[i + 1].second;
        }
        else{
            int k1 = mau(cur[i].first + 1, id);
            int k2 = mau(cur[i + 1].first - 1, id);
            int y = cur[i + 1].first - cur[i].first - 1;
            if(k1 + k2 <= 1){
                y /= 2;
                res = res + (sz*sz)*y;
            }
            else{
                y = (y + 1)/2;
                res = res + (sz*sz)*y;
            }
            if(i + 1==int(cur.size() - 1)) break;
            int col = mau(cur[i + 1].first, id);
            if(col==1) res = res + sz*sz - cur[i + 1].second;
            else res = res + cur[i + 1].second;
        }
    }
    return res;
}

int solve(int s){
    f1(i, s) v[i].clear();
    f1(i, k){
        int k1 = (a[i].first - 1)/s + 1;
        int k2 = (a[i].second - 1)/s + 1;
        v[k1].emplace_back(k2);
    }
    vector <pair <int, int> > now;
    f1(i, (n/s)){
        now.clear();
        now.emplace_back(0, s*s);
        for(int j = 0; j < v[i].size(); j++){
            int cur = j;
            int e = v[i][j];
            for(cur = j; cur < v[i].size(); cur++){
                if(v[i][cur] != v[i][j]) break;
            }
            now.emplace_back(v[i][j], cur - j);
            j = cur - 1;
            int u = v[i][j];
            int g = v[i][j];
        }
        now.emplace_back((n/s) + 1, s*s);
        f[i][0] = f[i][1] = 1e9;
        f[i][0] = solve2(now, s, 0);
        f[i][1] = solve2(now, s, 1);
    }
    int x1 = 0, x2 = 0;
    f1(i, (n/s)){
        if(i%2) x1 = x1 + f[i][1], x2 = x2 + f[i][0];
        else x1 = x1 + f[i][0], x2 = x2 + f[i][1];
    }
    return min(x1, x2);
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    v.resize(n + 1);
    f1(i, k){
        int x, y, u, v; cin >> x >> y >> u >> v;
        a[i] = {x, y};
    }
    sort(a + 1, a + k + 1);
    int res = 21e8;
    f1(i, sqrt(n)){
        int j = n/i;
        if(i*j==n){
            if(i != n)
            res = min(res, solve(i));
            if(j != n)
            res = min(res, solve(j));
        }
    }
    cout << res;
}

Compilation message (stderr)

chessboard.cpp: In function 'int solve2(std::vector<std::pair<int, int> >, int, int)':
chessboard.cpp:26:14: warning: variable 't' set but not used [-Wunused-but-set-variable]
         auto t = cur[i + 1];
              ^
chessboard.cpp:27:14: warning: variable 't2' set but not used [-Wunused-but-set-variable]
         auto t2 = cur[i];
              ^~
chessboard.cpp: In function 'int solve(int)':
chessboard.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < v[i].size(); j++){
                        ~~^~~~~~~~~~~~~
chessboard.cpp:71:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(cur = j; cur < v[i].size(); cur++){
                          ~~~~^~~~~~~~~~~~~
chessboard.cpp:70:17: warning: unused variable 'e' [-Wunused-variable]
             int e = v[i][j];
                 ^
chessboard.cpp:76:17: warning: unused variable 'u' [-Wunused-variable]
             int u = v[i][j];
                 ^
chessboard.cpp:77:17: warning: unused variable 'g' [-Wunused-variable]
             int g = v[i][j];
                 ^

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