Submission #85333

#	Time	Username	Problem	Language	Result	Execution time	Memory
85333		mra2322001	Chessboard (IZhO18_chessboard)	C++14	8 / 100	69 ms	5456 KiB

chessboard

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

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

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

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

ll solve2(vector <pair <ll, ll> > cur, ll sz, ll id){
    ll Sz = cur.size();
    ll res = 0;
    for(ll i = 0; i < Sz - 1; i++){
        auto t = cur[i + 1];
        auto t2 = cur[i];
        ll x = cur[i + 1].first - cur[i].first;
        if(x==1){
            if(i==Sz - 2) break;
            if(cur[i + 1].first > (n/sz)) continue;
            ll 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{
            ll k1 = mau(cur[i].first + 1, id);
            ll k2 = mau(cur[i + 1].first - 1, id);
            ll 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==ll(cur.size() - 1)) break;
            ll 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;
}

ll solve(ll s){
    f1(i, s) v[i].clear();
    f1(i, k){
        ll k1 = (a[i].first - 1)/s + 1;
        ll k2 = (a[i].second - 1)/s + 1;
        v[k1].emplace_back(k2);
    }
    vector <pair <ll, ll> > now;
    f1(i, (n/s)){
        now.clear();
        now.emplace_back(0, s*s);
        for(ll j = 0; j < v[i].size(); j++){
            ll cur = j;
            ll 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;
            ll u = v[i][j];
            ll 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);
    }
    ll 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){
        ll x, y, u, v; cin >> x >> y >> u >> v;
        a[i] = {x, y};
    }
    sort(a + 1, a + k + 1);
    ll res = 21e8;
    f1(i, sqrt(n)){
        ll 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 'll solve2(std::vector<std::pair<long long int, long long int> >, ll, ll)':
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 'll solve(ll)':
chessboard.cpp:68:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll 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:16: warning: unused variable 'e' [-Wunused-variable]
             ll e = v[i][j];
                ^
chessboard.cpp:76:16: warning: unused variable 'u' [-Wunused-variable]
             ll u = v[i][j];
                ^
chessboard.cpp:77:16: warning: unused variable 'g' [-Wunused-variable]
             ll 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