Submission #495154

#TimeUsernameProblemLanguageResultExecution timeMemory
495154NalrimetChessboard (IZhO18_chessboard)C++17
70 / 100
253 ms4244 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define ll long long const int N = 1e5 + 5; const ll inf = 1e18; long long n, k, x[N], y[N], cnt1, cnt2, m1, m2, ans = inf, b1, b2, s; vector<long long> v; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for(ll i = 1; i * i <= n; ++i){ if(n % i == 0){ v.pb(i); if(i != n / i) v.pb(n / i); } } for(ll i = 1, x1, y1; i <= k; ++i){ cin >> x[i] >> y[i]; cin >> x1 >> y1; } for(auto to : v){ if(to == n) continue; cnt1 = 0; cnt2 = 0; for(ll i = 1; i <= k; ++i){ b1 = (x[i] + to - 1) / to; b2 = (y[i] + to - 1) / to; if(b1 % 2) { if(b2 % 2) cnt1++; else cnt2++; } else { if(b2 % 2) cnt2++; else cnt1++; } } // cout << to << ' ' << cnt1 << ' ' << cnt2 << '\n'; s = n / to; // cout << s << '\n'; m1 = (s + 1) / 2 * ((s + 1) / 2) + (s / 2) * (s / 2); m2 = s * s - m1; // cout << m1 << ' ' << m2 << '\n'; m1 *= to * to; m2 *= to * to; // cout << m1 << ' ' << m2 << '\n'; ans = min(ans, min(m1 - cnt1 + cnt2, m2 - cnt2 + cnt1)); // cout << m1 - cnt1 + cnt2 << '\n' << m2 - cnt2 + cnt1 << '\n'; } 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...