Submission #942931

#TimeUsernameProblemLanguageResultExecution timeMemory
942931TeemkaChessboard (IZhO18_chessboard)C++17
39 / 100
60 ms3800 KiB
#include "bits/stdc++.h" #define F first #define S second #define ALL(a) a.begin() , a.end() #ifndef ONLINE_JUDGE #define OK cout << __LINE__ << "| "<< "---------------------------OK-----------------------" << endl; #define deb(x) cout << __LINE__ << "| "<< #x << " = " << x << endl; #else #define OK #define deb(x) #endif typedef long double ld; typedef long long ll; using namespace std ; const ll N = 1e3 + 7 ; const ll INF = 1e9; const ll mod = 1e9 + 7 ; const double eps = 1e-9 ; const int dx[] = { 0 , 0 , 1 , -1, 1 , -1 , 1 , -1} , dy[] = {1 , -1 , 0 , 0 , 1 , 1, -1 , -1} ; int n, k; struct query{ int x1, x2 ,y1 ,y2; query(int _x1, int _x2 ,int _y1, int _y2){ x1 = _x2, x2 = _x2, y1 = _y1, y2 = _y2; } }; vector<query> vec; void test_solve(int test_index){ cin >> n >> k; for(int i = 1; i <= k; i++){ int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; vec.push_back(query(x1 , x2 ,y1 ,y2)); } int ans = INF; for(int i = 1; i < n; i++){ if(n % i) continue; int cnt[2] = {0 , 0}; for(auto [x1 ,x2 ,y1, y2] : vec){ int dnt[2] = {0 , 0}; for(int j = x1; j <= x2; j++){ if((j - 1) / i % 2){ dnt[1]++; } else{ dnt[0]++; } } for(int j = y1; j <= y2; j++){ if((j - 1) / i % 2){ cnt[1] += dnt[0]; cnt[0] += dnt[1]; } else{ cnt[0] += dnt[0]; cnt[1] += dnt[1]; } } } int d = n / i , less , big; if(d % 2){ less = (d * d - 1) / 2 * (i * i); big = less + i * i; } else{ less = (d * d) / 2 * (i * i); big = less; } // deb(big); // deb(less); // deb(cnt[0]); // deb(cnt[1]); // deb(i); ans = min({ans, (big - cnt[0]) + cnt[1] , cnt[0] + (less- cnt[1])}); } cout << ans << endl; } signed main(){ ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0); int test = 1; //cin >> test ; for(int i = 1 ; i <= test ; i++){ // cout << "Case " << i << ": " ; test_solve(i) ; } 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...