제출 #689594

#제출 시각아이디문제언어결과실행 시간메모리
689594YENGOYANChessboard (IZhO18_chessboard)C++17
70 / 100
550 ms4252 KiB
/* //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\ \\ // // 271828___182845__904523__53602__ \\ \\ 87___47____13______52____66__24_ // // 97___75____72______47____09___36 \\ \\ 999595_____74______96____69___67 // // 62___77____24______07____66__30_ \\ \\ 35___35____47______59____45713__ // // \\ \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\// */ #include <iostream> #include <vector> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <cmath> #include <climits> #include <algorithm> #include <random> #include <queue> #include <deque> #include <iomanip> #include <string> #include <tuple> #include <bitset> #include <chrono> #include <ctime> #include <fstream> #include <stack> #include <cstdio> using namespace std; using ll = long long; const int N = 3e5 + 5; const ll mod = 1e9 + 7, inf = 1e18; struct rec { ll x1, y1, x2, y2; }; bool ev_od(ll x, ll y, ll side) { ll xx = (x + side - 1) / side, yy = (y + side - 1) / side; if (xx % 2 == yy % 2) return 0; return 1; } void solve() { ll n, k; cin >> n >> k; vector<rec> v(k); for (int i = 0; i < k; ++i) { cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2; } ll ans = n * n; for (int i = 1; i < n; ++i) { if (n % i) continue; ll od = 0, ev = 0; for (rec& ii : v) { ll xx2 = (ii.x2 - 1) / i * i; ll xx1 = (ii.x1 - 1) / i * i; ll yy2 = (ii.y2 - 1) / i * i; ll yy1 = (ii.y1 - 1) / i * i; ++xx1, ++yy1; ++xx2, ++yy2; //cout << xx1 << " " << yy1 << " " << xx2 << " " << yy2 << "\n"; //if(i == 2) cout << xx1 << " " << yy1 << " " << xx2 << " " << yy2 << "\n"; if (xx1 < xx2 && yy1 < yy2) { ll ynd = (xx2 - xx1 + 1) / i * (yy2 - yy1 + 1) / i; ev += (ynd + ((xx1 / i) % 2 == (yy1 / i) % 2)) / 2 * i * i; od += (ynd + ((xx1 / i) % 2 != (yy1 / i) % 2)) / 2 * i * i; // bajnel vec uxankyan // dzax verev if (ev_od(ii.x1, ii.y1, i)) { od += (xx1 - ii.x1) * (yy1 - ii.y1); } else { ev += (xx1 - ii.x1) * (yy1 - ii.y1); } // aj verev if (ev_od(xx2, ii.y1, i)) { od += (yy1 - ii.y1) * (ii.x2 - xx2); } else { ev += (yy1 - ii.y1) * (ii.x2 - xx2); } // verev mejtex ll h = yy1 - ii.y1; if (ev_od(xx1, ii.y1, i)) { ll w = xx2 - xx1, c = w / i; od += (c + 1) / 2 * h * i; ev += c / 2 * h * i; } else { ll w = xx2 - xx1, c = w / i; od += c / 2 * h * i; ev += (c + 1) / 2 * h * i; } // mejtex dzax ll w = xx1 - ii.x1; if (ev_od(ii.x1, yy1, i)) { ll h = yy2 - yy1, c = h / i; od += (c + 1) / 2 * w * i; ev += c / 2 * w * i; } else { ll h = yy2 - yy1, c = h / i; od += c / 2 * w * i; ev += (c + 1) / 2 * w * i; } // mejtex aj w = ii.x2 - xx2; if (ev_od(xx2, yy1, i)) { ll h = yy2 - yy1, c = h / i; od += (c + 1) / 2 * w * i; ev += c / 2 * w * i; } else { ll h = yy2 - yy1, c = h / i; od += c / 2 * w * i; ev += (c + 1) / 2 * w * i; } // dzax var if (ev_od(ii.x1, yy2, i)) { od += (xx1 - ii.x1) * (ii.y2 - yy2); } else { ev += (xx1 - ii.x1) * (ii.y2 - yy2); } // aj var if (ev_od(xx2, yy2, i)) { od += (ii.x2 - xx2) * (ii.y2 - yy2); } else { ev += (ii.x2 - xx2) * (ii.y2 - yy2); } // var mejtex h = ii.y2 - yy2; if (ev_od(xx1, yy2, i)) { ll w = xx2 - xx1, c = w / i; od += (c + 1) / 2 * h * i; ev += c / 2 * h * i; } else { ll w = xx2 - xx1, c = w / i; od += c / 2 * h * i; ev += (c + 1) / 2 * h * i; } } /* 6 3 1 3 1 3 1 4 1 4 2 3 2 3 */ else if (xx1 >= xx2 && yy1 >= yy2) { //if(i == 2) cout << "DEBUG\n"; // bajnel petq che, patasxany hashvac e //cout << "DEBUG\n"; if (ev_od(ii.x1, ii.y1, i)) { od += (ii.x2 - ii.x1 + 1) * (ii.y2 - ii.y1 + 1); } else { ev += (ii.x2 - ii.x1 + 1) * (ii.y2 - ii.y1 + 1); } } else if (xx1 >= xx2) { // bajnel ireq uxxankyan, verevi u vari masy arandzin, mejtexy arandzin // verevi masy if (ev_od(ii.x1, ii.y1, i)) { od += (yy1 - ii.y1) * (ii.x2 - ii.x1); } else { ev += (yy1 - ii.y1) * (ii.x2 - ii.x1); } // vari masy if (ev_od(ii.x1, yy2, i)) { od += (ii.y2 - yy2) * (ii.x2 - ii.x1); } else { ev += (ii.y2 - yy2) * (ii.x2 - ii.x1); } // mejtexi masy ll h = yy2 - yy1, c = h / i; if (ev_od(ii.x1, yy1, i)) { od += (c + 1) / 2 * i * (ii.x2 - ii.x1); ev += c / 2 * i * (ii.x2 - ii.x1); } else { od += c / 2 * i * (ii.x2 - ii.x1); ev += (c + 1) / 2 * i * (ii.x2 - ii.x1); } } else { // bajnel ireq uxxankyan, dzax u aj masy arandzin, mejtexy arandzin // dzax masy if (ev_od(ii.x1, ii.y1, i)) { od += (ii.x2 - ii.x1) * (ii.y2 - ii.y1); } else { ev += (ii.x2 - ii.x1) * (ii.y2 - ii.y1); } // aj masy if (ev_od(xx2, ii.y1, i)) { od += (ii.x2 - xx2) * (ii.y2 - ii.y1); } else { ev += (ii.x2 - xx2) * (ii.y2 - ii.y1); } // mejtexi masy ll w = xx2 - xx1, c = w / i; if (ev_od(xx1, ii.y1, i)) { od += (c + 1) / 2 * i * (ii.y2 - ii.y1); ev += c / 2 * i * (ii.y2 - ii.y1); } else { od += c / 2 * i * (ii.y2 - ii.y1); ev += (c + 1) / 2 * i * (ii.y2 - ii.y1); } } } ll edge = n / i, c = (edge * edge + 1) / 2; ll a = od + c * i * i - ev; c = edge * edge / 2; ll b = ev + c * i * i - od; ans = min({ ans, a, b }); } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); //int t; cin >> t; //while (t--) solve(); }
#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...