Submission #3659669
Source Code Expand
/** * File : D.cpp * Author : Kazune Takahashi * Created : 11/24/2018, 9:16:13 PM * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <functional> #include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725)); #include <chrono> // std::chrono::system_clock::time_point start_time, end_time; // start = std::chrono::system_clock::now(); // double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count(); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; int N; ll D; typedef tuple<ll, ll> P; vector<P> V; typedef tuple<ll, ll, ll> X; vector<X> W; set<ll> A[2]; int cnt[1010][1010]; ll calc(ll x) { ll lb = 0; ll ub = 100010; while (ub - lb > 1) { ll t = (ub + lb) / 2; if (t * t < x) { lb = t; } else { ub = t; } } return ub - 1; } ll calc_(int k) { if ((int)A[k].size() <= 1) { return 0; } auto it = A[k].begin(); auto it2 = A[k].begin(); it2++; auto last = A[k].end(); last--; ll mini = *last - *it; while (it2 != A[k].end()) { mini = min(mini, D - (*it2 - *it)); it++; it2++; } return mini; } int main() { cin >> N >> D; for (auto i = 0; i < N; i++) { ll x, y; cin >> x >> y; V.push_back(P(x, y)); } fill(&cnt[0][0], &cnt[0][0] + 1010 * 1010, 0); for (auto i = 0; i < N; i++) { ll x = get<0>(V[i]); ll y = get<1>(V[i]); cnt[x % D][y % D]++; } for (auto i = 0; i < D; i++) { for (auto j = 0; j < D; j++) { if (cnt[i][j] > 0) { W.push_back(X(cnt[i][j], i, j)); } } } sort(W.begin(), W.end()); reverse(W.begin(), W.end()); ll maxi = get<0>(W[0]); ll r = calc(maxi); ll s = (maxi + r) / (r + 1) - 1; for (auto e : W) { if (get<0>(e) < (r + 1) * (s + 1)) { break; } A[0].insert(get<1>(e)); A[1].insert(get<2>(e)); } /* for (auto i = 0; i < D; i++) { for (auto j = 0; j < D; j++) { cerr << cnt[i][j] << " "; } cerr << endl; } cerr << "maxi = " << maxi << endl; cerr << "r = " << r << ", s = " << s << endl; */ ll alpha = calc_(0); ll beta = calc_(1); // cerr << "alpha = " << alpha << ", beta = " << beta << endl; ll ans = max(min(alpha, beta) + r * D, max(alpha, beta) + s * D); cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Square Rotation |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3109 Byte |
Status | WA |
Exec Time | 76 ms |
Memory | 10352 KB |
Judge Result
Set Name | All | small | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 300 | 0 / 500 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 01_corner2_00, 01_corner2_01, 01_corner2_02, 01_corner2_03, 01_corner_00, 01_corner_01, 01_corner_02, 01_corner_03, 01_corner_04, 01_corner_05, 01_corner_06, 01_corner_07, 01_corner_08, 01_corner_09, 01_corner_10, 01_corner_11, 01_corner_12, 01_corner_13, 01_corner_14, 01_corner_15, 01_corner_16, 01_small1_00, 01_small1_01, 01_small1_02, 01_small1_03, 01_small1_04, 01_small2_00, 01_small2_01, 01_small2_02, 01_small3_00, 01_small3_01, 01_small3_02, 01_small3_03, 01_small3_04, 01_small4_00, 01_small4_01, 01_small4_02, 01_small5_00, 01_small5_01, 01_small5_02, 01_small5_03, 01_small5_04, 02_corner2_00, 02_corner2_01, 02_corner2_02, 02_corner2_03, 02_corner_00, 02_corner_01, 02_corner_02, 02_corner_03, 02_large1_00, 02_large1_01, 02_large1_02, 02_large1_03, 02_large1_04, 02_large2_00, 02_large2_01, 02_large2_02, 02_large3_00, 02_large3_01, 02_large3_02, 02_large3_03, 02_large3_04, 02_large4_00, 02_large4_01, 02_large4_02 |
small | 01_corner2_00, 01_corner2_01, 01_corner2_02, 01_corner2_03, 01_corner_00, 01_corner_01, 01_corner_02, 01_corner_03, 01_corner_04, 01_corner_05, 01_corner_06, 01_corner_07, 01_corner_08, 01_corner_09, 01_corner_10, 01_corner_11, 01_corner_12, 01_corner_13, 01_corner_14, 01_corner_15, 01_corner_16, 01_small1_00, 01_small1_01, 01_small1_02, 01_small1_03, 01_small1_04, 01_small2_00, 01_small2_01, 01_small2_02, 01_small3_00, 01_small3_01, 01_small3_02, 01_small3_03, 01_small3_04, 01_small4_00, 01_small4_01, 01_small4_02, 01_small5_00, 01_small5_01, 01_small5_02, 01_small5_03, 01_small5_04, 01_corner2_00, 01_corner2_01, 01_corner2_02, 01_corner2_03, 01_corner_00, 01_corner_01, 01_corner_02, 01_corner_03, 01_corner_04, 01_corner_05, 01_corner_06, 01_corner_07, 01_corner_08, 01_corner_09, 01_corner_10, 01_corner_11, 01_corner_12, 01_corner_13, 01_corner_14, 01_corner_15, 01_corner_16, 02_corner2_00, 02_corner2_01, 02_corner2_02, 02_corner2_03, 02_corner_00, 02_corner_01, 02_corner_02, 02_corner_03 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 3 ms | 4224 KB |
00_sample_01 | AC | 3 ms | 4224 KB |
00_sample_02 | AC | 3 ms | 4224 KB |
01_corner2_00 | AC | 4 ms | 4224 KB |
01_corner2_01 | AC | 5 ms | 4352 KB |
01_corner2_02 | AC | 9 ms | 4480 KB |
01_corner2_03 | AC | 45 ms | 5236 KB |
01_corner_00 | AC | 4 ms | 4224 KB |
01_corner_01 | WA | 13 ms | 4604 KB |
01_corner_02 | WA | 23 ms | 4856 KB |
01_corner_03 | WA | 16 ms | 4600 KB |
01_corner_04 | AC | 9 ms | 4480 KB |
01_corner_05 | WA | 27 ms | 4852 KB |
01_corner_06 | WA | 5 ms | 4352 KB |
01_corner_07 | WA | 6 ms | 4480 KB |
01_corner_08 | AC | 39 ms | 5108 KB |
01_corner_09 | WA | 3 ms | 4224 KB |
01_corner_10 | WA | 4 ms | 4352 KB |
01_corner_11 | WA | 3 ms | 4224 KB |
01_corner_12 | AC | 5 ms | 4352 KB |
01_corner_13 | WA | 29 ms | 4980 KB |
01_corner_14 | WA | 7 ms | 4480 KB |
01_corner_15 | WA | 5 ms | 4352 KB |
01_corner_16 | AC | 9 ms | 4476 KB |
01_small1_00 | AC | 76 ms | 5616 KB |
01_small1_01 | WA | 53 ms | 5364 KB |
01_small1_02 | WA | 19 ms | 4728 KB |
01_small1_03 | AC | 62 ms | 5488 KB |
01_small1_04 | WA | 46 ms | 5236 KB |
01_small2_00 | WA | 14 ms | 4728 KB |
01_small2_01 | AC | 3 ms | 4224 KB |
01_small2_02 | WA | 9 ms | 4604 KB |
01_small3_00 | AC | 3 ms | 4224 KB |
01_small3_01 | WA | 4 ms | 4224 KB |
01_small3_02 | WA | 12 ms | 4728 KB |
01_small3_03 | WA | 8 ms | 4476 KB |
01_small3_04 | WA | 3 ms | 4224 KB |
01_small4_00 | WA | 54 ms | 5872 KB |
01_small4_01 | AC | 3 ms | 4224 KB |
01_small4_02 | AC | 3 ms | 4224 KB |
01_small5_00 | AC | 3 ms | 4224 KB |
01_small5_01 | AC | 3 ms | 4224 KB |
01_small5_02 | AC | 3 ms | 4224 KB |
01_small5_03 | AC | 3 ms | 4224 KB |
01_small5_04 | AC | 3 ms | 4224 KB |
02_corner2_00 | AC | 6 ms | 4480 KB |
02_corner2_01 | AC | 13 ms | 4604 KB |
02_corner2_02 | AC | 16 ms | 4600 KB |
02_corner2_03 | AC | 4 ms | 4352 KB |
02_corner_00 | AC | 4 ms | 4224 KB |
02_corner_01 | WA | 5 ms | 4352 KB |
02_corner_02 | WA | 19 ms | 4728 KB |
02_corner_03 | WA | 3 ms | 4224 KB |
02_large1_00 | WA | 18 ms | 5052 KB |
02_large1_01 | WA | 58 ms | 6516 KB |
02_large1_02 | WA | 9 ms | 4608 KB |
02_large1_03 | WA | 53 ms | 5364 KB |
02_large1_04 | WA | 16 ms | 4924 KB |
02_large2_00 | AC | 6 ms | 4480 KB |
02_large2_01 | AC | 4 ms | 4352 KB |
02_large2_02 | AC | 15 ms | 5752 KB |
02_large3_00 | AC | 6 ms | 4480 KB |
02_large3_01 | WA | 58 ms | 5872 KB |
02_large3_02 | WA | 57 ms | 5872 KB |
02_large3_03 | WA | 54 ms | 5872 KB |
02_large3_04 | WA | 59 ms | 5872 KB |
02_large4_00 | WA | 65 ms | 5872 KB |
02_large4_01 | AC | 66 ms | 5872 KB |
02_large4_02 | AC | 67 ms | 10352 KB |