Submission #343846

#TimeUsernameProblemLanguageResultExecution timeMemory
343846emil_physmathChessboard (IZhO18_chessboard)C++17
100 / 100
1515 ms4728 KiB
/*#include <iostream> #include <stdio.h> using namespace std; const int MAXK=100005; long long mini[MAXK], maxi[MAXK], minj[MAXK], maxj[MAXK]; long long NumWhite(long long, long long, long long, long long, long long cellLen); long long FindAns(long long n, long long k, long long cellLen); int main() { long long n, k; cin>>n>>k; for (int i=0; i<k; i++) scanf("%lld%lld%lld%lld", mini+i, minj+i, maxi+i, maxj+i); long long ans=n*n; for (int cellLen=1; cellLen*cellLen<=n; cellLen++) if (n%cellLen==0) { ans=min(ans, FindAns(n, k, cellLen)); ans=min(ans, FindAns(n, k, n/cellLen)); } cout<<ans<<'\n'; char I; cin >> I; return 0; } long long FindAns(long long n, long long k, long long cellLen) { if (cellLen>=n) return n*n; long long shouldWhite=0, shouldBlack=0, isBlack=0; for (int i=0; i<k; i++) { shouldWhite+=NumWhite(mini[i], minj[i], maxi[i], maxj[i], cellLen); isBlack+=(maxi[i]-mini[i]+1)*(maxj[i]-minj[i]+1); } shouldBlack=(n*n-NumWhite(1, 1, n, n, cellLen))-(isBlack-shouldWhite); return min(shouldWhite+shouldBlack, n*n-(shouldWhite+shouldBlack)); } using ll = long long; struct el { ll a, b, c, d; }; ll prefans(ll x, ll y, ll k, ll f) { ll ans; ll ab = y / k, a; a = (ab + 1) / 2; a *= k; if (ab % 2 == 0) a += y % k; if (x <= k) ans = x * a; else { ll aa = y - a; ll q = x / k; ans = aa * (q / 2) * k; ans += a * ((q + 1) / 2) * k; if (q % 2) ans += aa * (x % k); else ans += a * (x % k); } if (f == 1) return ans; else return x * y - ans; } ll rect(el s, ll d, int f) { ll mec = prefans(s.c, s.d, d, f) - (s.c * s.d - prefans(s.c, s.d, d, f)); ll poqr = prefans(s.a, s.b, d, f) - (s.a * s.b - prefans(s.a, s.b, d, f));; return mec - poqr; } long long NumWhite(long long mini, long long minj, long long maxi, long long maxj, long long len) { if (!mini) mini=1; if (!minj) minj=1; return rect(el{mini, minj, maxi, maxj}, len, 1); if (mini==1 && minj==1) { return prefans(maxi, maxj, len, 1); long long ans=0, i=maxi, j=maxj; ans+=len*len*(((i/len)*(j/len)+1)/2); if ((i/len)%2) ans+=(i%len)*((j/len)/2)*len; else ans+=(i%len)*((j/len+1)/2)*len; if ((j/len)%2) ans+=(j%len)*((i/len)/2)*len; else ans+=(j%len)*((i/len+1)/2)*len; if ((i/len)%2==(j/len)%2) ans+=(i%len)*(j%len); return ans; } return NumWhite(1, 1, maxi, maxj, len)- NumWhite(1, 1, maxi, minj-1, len)-NumWhite(1, 1, mini-1, maxj, len)+ NumWhite(1, 1, mini-1, minj-1, len); }*/ #include <iostream> #include <algorithm> #include <vector> using namespace std; using ll = long long; struct el { ll a, b, c, d; }; vector<ll> dv; vector<el> points; ll ans; ll prefans(ll x, ll y, ll k, int f) { ll ans; ll ab = y / k, a; a = (ab + 1) / 2; a *= k; if (ab % 2 == 0) a += y % k; if (x <= k) ans = x * a; else { ll aa = y - a; ll q = x / k; ans = aa * (q / 2) * k; ans += a * ((q + 1) / 2) * k; if (q % 2) ans += aa * (x % k); else ans += a * (x % k); } if (f == 1) return ans; else return x * y - ans; } ll rect(ll x, ll y, ll d, int f) { return prefans(x, y, d, f) - (x * y - prefans(x, y, d, f)); } int main() { ll n, k; cin >> n >> k; ans = n * n; for (int i = 1; i < n; i++) if (n % i == 0)dv.push_back(i); for (int i = 0; i < k; i++) { ll a, b, c, d; cin >> a >> b >> c >> d; points.push_back({ a,b,c,d }); }/* for (auto p : points) cerr << p.first << ' ' << p.second << '\n';*/ for (ll d : dv) { ll blackans; ll q = n / d; if (q % 2) blackans = (n * n - d * d) / 2 + d * d; else blackans = n * n / 2; ll whiteans = n * n - blackans; whiteans = prefans(n, n, d, 1); blackans = prefans(n, n, d, 0); for (auto p : points) { whiteans += rect(p.c, p.d, d, 0) - rect(p.a - 1, p.d, d, 0) - rect(p.c, p.b - 1, d, 0) + rect(p.a - 1, p.b - 1, d, 0); blackans += rect(p.c, p.d, d, 1) - rect(p.a - 1, p.d, d, 1) - rect(p.c, p.b - 1, d, 1) + rect(p.a - 1, p.b - 1, d, 1); } ans = min(ans, min(blackans, whiteans)); } cout << ans; return 0; }
#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...