Submission #85333

#TimeUsernameProblemLanguageResultExecution timeMemory
85333mra2322001Chessboard (IZhO18_chessboard)C++14
8 / 100
69 ms5456 KiB
#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];
                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...