QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#577062 | #9314. The Median of the Median of the Median | FlowRays | AC ✓ | 181ms | 34648kb | C++20 | 9.2kb | 2024-09-20 00:57:49 | 2024-09-20 00:57:49 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ve vector
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vpi = vector<vector<pii>>;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 2e5+10;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO
struct IO {
#ifdef FIO
const static int BUFSIZE = 1 << 20; char buf[BUFSIZE], obuf[BUFSIZE], *p1, *p2, *pp; inline char getchar() { return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++); } inline void putchar(char x) { ((pp - obuf == BUFSIZE && (fwrite(obuf, 1, BUFSIZE, stdout), pp = obuf)), *pp = x, pp++); } inline IO &flush() { fwrite(obuf, 1, pp - obuf, stdout); fflush(stdout); return *this; } IO() { p1 = buf, p2 = buf, pp = obuf; } ~IO() { flush(); }
#else
int (*getchar)() = &::getchar; int (*putchar)(int) = &::putchar; inline IO &flush() { fflush(stdout); return *this; };
#endif
string sep = " "; int k = 2; template <typename T, typename std::enable_if<std::is_integral<T>::value || std::is_same<T, __int128_t>::value>::type * = nullptr> inline int r(T &s) { int f = 1; char ch = getchar(); s = 0; while (!isdigit(ch) && ch != EOF) f = (ch == '-' ? -1 : 1), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); s *= f; return ch != EOF; } template <typename T> inline bool r(vector<T> &v) { bool f = true; for(auto &x: v) f &= r(x); return f; } template <typename T> inline bool rv(vector<T> &v, int x = 1) { bool f = true; for (int i = x; i < v.size(); ++i) f &= r(v[i]); return f; } template <typename T, typename enable_if<is_floating_point<T>::value>::type * = nullptr> inline int r(T &s) { int f = 1; char ch = getchar(); s = 0; while (!isdigit(ch) && ch != EOF && ch != '.') f = (ch == '-' ? -1 : 1), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); if (ch == EOF) return false; if (ch == '.') { T eps = 0.1; ch = getchar(); while (isdigit(ch)) s = s + (ch ^ 48) * eps, ch = getchar(), eps /= 10; } s *= f; return ch != EOF; } inline int r(char &c) { char ch = getchar(); c = EOF; while (isspace(ch) && ch != EOF) ch = getchar(); if (ch != EOF) c = ch; return c != EOF; } inline int r(char *c) { char ch = getchar(), *s = c; while (isspace(ch) && ch != EOF) ch = getchar(); while (!isspace(ch) && ch != EOF) *(c++) = ch, ch = getchar(); *c = '\0'; return s != c; } inline int r(string &s) { s.clear(); char ch = getchar(); while (isspace(ch) && ch != EOF) ch = getchar(); while (!isspace(ch) && ch != EOF) s += ch, ch = getchar(); return s.size() > 0; } inline int getline(char *c, const char &ed = '\n') { char ch = getchar(), *s = c; while (ch != ed && ch != EOF) *(c++) = ch, ch = getchar(); *c = '\0'; return s != c; } inline int getline(string &s, const char &ed = '\n') { s.clear(); char ch = getchar(); while (ch != ed && ch != EOF) s += ch, ch = getchar(); return s.size() > 0; } template <typename T = int> inline T r() { T x; r(x); return x; } template <typename T, typename... Ts> int r(T &x, Ts &...val) { return r(x) && r(val...); } template <typename T, typename enable_if<is_integral<T>::value>::type * = nullptr> IO &w(T x) { if (x < 0) putchar('-'), x = -x; static char sta[20]; int top = 0; do sta[top++] = x % 10 + '0', x /= 10; while (x); while (top) putchar(sta[--top]); return *this; } inline IO &w(const string &str) { for (char ch : str) putchar(ch); return *this; } inline IO &w(const char *str) { while (*str != '\0') putchar(*(str++)); return *this; } inline IO &w(char *str) { return w((const char *)str); } inline IO &w(const char &ch) { return putchar(ch), *this; } template <typename T, typename enable_if<is_floating_point<T>::value>::type * = nullptr> inline IO &w(T x) { if (x > 1e18 || x < -1e18) { w("[Floating point overflow]"); throw; } if (x < 0) putchar('-'), x = -x; const static long long pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 100000000000000000, 100000000000000000}; const auto &n = pow10[k]; long long whole = (int)x; double tmp = (x - whole) * n; long long frac = tmp; double diff = tmp - frac; if (diff > 0.5) { ++frac; if (frac >= n) frac = 0, ++whole; } else if (diff == 0.5 && ((frac == 0U) || (frac & 1U))) ++frac; w(whole); if (k == 0U) { diff = x - (double)whole; if ((!(diff < 0.5) || (diff > 0.5)) && (whole & 1)) ++whole; } else { putchar('.'); static char sta[20]; int count = k, top = 0; while (frac) { sta[top++] = frac % 10 + '0'; frac /= 10, count--; } while (count--) putchar('0'); while (top) putchar(sta[--top]); } return *this; } template <typename T> inline IO &w(vector<T> &v) { bool f = true; for(auto x: v) { if (f) f = false; else w(sep); w(x); }; return *this; } template <typename T> inline IO &wv(vector<T> &v,int x = 1) { bool f = true; for (int i = x; i < v.size(); ++i) { if (f) f = false; else w(sep); w(v[i]); }; wl(); return *this; } template <typename T, typename... Ts> inline IO &w(T x, Ts... val) { w(x); w(sep); w(val...); return *this; } template <typename... Ts> inline IO &wl(Ts... val) { w(val...); putchar('\n'); return *this; } inline IO &wl(void) { putchar('\n'); return *this; } template <typename T> inline IO &ww(T x, const string &s = " ") { w(x), w(s); return *this; } inline IO &ss(const string &s) { return sep = s, *this; } inline IO &sp(const int &K) { return k = K, *this; }
} io;
struct ER {
#define debug(x...) cerr << "Line " << __LINE__ << ": " #x " = "; er.wl(x)
#define debug_assert(a, x...) if (not(a)) { cerr << "Line " << __LINE__ << ": Assertion `" #a "` failed." << endl; cerr << #x " = "; er.wl(x); exit(0);}
string sep = " "; template <typename T, typename enable_if<is_integral<T>::value>::type * = nullptr> ER &w(T x) { cerr << x; return *this; } inline ER &w(const string &str) { cerr << str; return *this; } inline ER &w(const char *str) { cerr << str; return *this; } inline ER &w(char *str) { return w((const char *)str); } inline ER &w(const char &ch) { cerr << ch; return *this; } template <typename T, typename enable_if<is_floating_point<T>::value>::type * = nullptr> inline ER &w(T x) { cerr << x; return *this; } template <typename A, typename B> inline ER &w(pair<A, B> x) { cerr << "("; w(x.fi); cerr << ", "; w(x.se); cerr << ")"; return *this; } template <typename T, size_t N> inline ER &w(array<T, N> &a) { cerr << "["; bool first = true; for (auto &v : a) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "]"; return *this; } template <typename T> inline ER &w(vector<T> &x) { cerr << "["; bool first = true; for (auto &v : x) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "]"; return *this; } template <typename T, class Cmp> inline ER &w(set<T, Cmp> &x) { cerr << "{"; bool first = true; for (auto &v : x) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "}"; return *this; } template <typename T, class Cmp> inline ER &w(multiset<T, Cmp> &x) { cerr << "{"; bool first = true; for (auto &v : x) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "}"; return *this; } template <typename A, typename B, class Cmp> inline ER &w(map<A, B, Cmp> &x) { cerr << "{"; bool first = true; for (auto &[a, b] : x) { cerr << (first ? "" : ", "); w(a); cerr << ": "; w(b); first = 0; } cerr << "}"; return *this; } template <typename T, typename... Ts> inline ER &w(T x, Ts... val) { w(x); w(sep); w(val...); return *this; } template <typename... Ts> inline ER &wl(Ts... val) { w(val...); cerr << endl; return *this; } inline ER &wl(void) { cerr << endl; return *this; } template <typename T> inline ER &ww(T x, const string &s = " ") { w(x), w(s); return *this; } inline ER &ss(const string &s) { return sep = s, *this; } inline ER &sp(const int &K) { cerr << fixed << setprecision(K); return *this; }
} er;
int main() {
int n;
io.r(n);
vi a(n+1);
io.rv(a);
vi v;
fore(i,1,n) v.pb(a[i]);
sort(all(v));
v.erase(unique(all(v)),v.end());
int l = 0, r = int(v.size())-1;
auto check = [&](int id) {
int x = v[id];
vi pre(n+1);
fore(i,1,n) pre[i] = pre[i-1] + (a[i] <= x ? -1 : 1);
vii b(n+1,vi(n+1));
fore(i,1,n) {
fore(j,i,n) {
b[i][j] = (pre[j]-pre[i-1] <= 0 ? -1 : 1);
}
}
vii pre2(n+1,vi(n+1));
fore(i,1,n) {
fore(j,1,n) {
pre2[i][j] = pre2[i][j-1] + pre2[i-1][j] - pre2[i-1][j-1] + b[i][j];
}
}
int cnt = 0;
fore(i,1,n) {
fore(j,i,n) {
int t = pre2[j][j] - pre2[i-1][j] - pre2[j][i-1] + pre2[i-1][i-1];
if(t <= 0) cnt--;
else cnt++;
}
}
return cnt <= 0;
};
while(l < r) {
int m = l+r >> 1;
if(check(m)) r = m;
else l = m+1;
}
io.wl(v[l]);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
4 1 3 1 7
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
8 3 3 8 4 5 3 8 5
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 159ms
memory: 31216kb
input:
1883 935804604 209383625 842052635 830082014 365721046 29571412 503828250 261878653 304868479 615753663 149387882 137293208 553441715 659054561 809401479 786598486 257715598 738987349 749751119 675212261 214984147 816730618 204108936 529505526 670681192 375128179 445679706 531625791 954119640 739969...
output:
484006473
result:
ok 1 number(s): "484006473"
Test #4:
score: 0
Accepted
time: 166ms
memory: 33248kb
input:
1957 872909724 707949349 490997221 189511043 696381097 482433184 174043836 548201426 788208141 757294560 536411878 361961 65102705 599648900 120639869 620050728 789988994 932102606 540785122 931710164 286821745 583586084 633444407 849735317 780584308 266550416 98570723 722783990 500921667 819344705 ...
output:
516436748
result:
ok 1 number(s): "516436748"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
178 692096263 317825236 931010188 434850173 52089022 326215531 68436615 315432237 122955263 641096948 348783853 876201150 853561741 370774198 822929299 828427226 546309487 178339038 549855187 410459983 953700209 566391036 649762057 955693969 976755106 277332611 380022551 211888435 42883285 988396877...
output:
593518959
result:
ok 1 number(s): "593518959"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
173 69392871 816390960 874922071 794279201 87781777 334366903 738652201 601755009 166103436 192703253 735807848 589526799 219998539 16401241 279391882 366912172 228325988 371454295 781080678 111668287 170762000 333246502 638906040 570891055 791690926 463722145 178137760 257822443 589685312 67772391 ...
output:
408439899
result:
ok 1 number(s): "408439899"
Test #7:
score: 0
Accepted
time: 175ms
memory: 34648kb
input:
2000 844787697 717725741 297174490 620713157 869654860 100305714 252182391 350740797 989692676 884515006 283929742 228386094 243395665 931009658 504278816 417368345 996825244 840349536 30435490 464970260 925567493 320798785 588704893 225104969 963755486 262212671 155822732 272322421 979407661 217426...
output:
493853563
result:
ok 1 number(s): "493853563"
Test #8:
score: 0
Accepted
time: 181ms
memory: 34588kb
input:
2000 125514461 95022349 795740214 269657744 524051185 725933061 555301058 20956383 570982744 927663180 130503343 910377386 251688610 442670648 444873155 283896336 535310191 667590228 223550748 256004263 626775796 392636383 500784551 509216248 283985276 517339979 342212266 70437630 465533157 91397139...
output:
477878585
result:
ok 1 number(s): "477878585"
Extra Test:
score: 0
Extra Test Passed