Submission #962449

#TimeUsernameProblemLanguageResultExecution timeMemory
962449CookieChessboard (IZhO18_chessboard)C++14
70 / 100
199 ms17492 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; const ll mod = 1e9 + 7, pr = 31; const int mxn = 5e5 + 5, mxq = 1e5 + 5, sq = 450, mxv = 5e4 + 1; //const int base = (1 <<18); const ll inf = 1e10 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // have fun! ll n, k; ll ans = inf; ll x[mxn + 1], y[mxn + 1], x2[mxn + 1], y2[mxn + 1]; void solve(int cand){ ll odd = 0, even = 0; for(int i = 1; i <= k; i++){ ll sm = x[i] / cand + y[i] / cand; if(sm & 1)odd++; else even++; } ll totodd = 0, toteven = 0; if((n / cand) & 1){ toteven = (n * n / (cand * cand) + 1) / 2 * cand * cand; totodd = (n * n / (cand * cand)) / 2 * cand * cand; }else{ toteven = (n * n / (cand * cand)) / 2 * cand * cand; totodd = (n * n / (cand * cand)) / 2 * cand * cand; } //cout << cand << " " << abs(toteven - even) + k - even << " " << abs(totodd - odd) + k - odd << "\n"; ans = min(ans, min(abs(toteven - even) + k - even, abs(totodd - odd) + k - odd)); } void solve(){ cin >> n >> k; for(int i = 1; i <= k; i++){ cin >> x[i] >> y[i] >> x2[i] >> y2[i]; --x[i]; --y[i]; --x2[i]; --y2[i]; } for(int i = 1; i < n; i++){ if(n % i == 0){ solve(i); } } cout << ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("netw.inp", "r", stdin); //freopen("netw.out", "w", stdout) int tt; tt = 1; while(tt--){ solve(); } 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...