QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#752954 | #5983. Pretty Good Proportion | Floze3 | 27 ✓ | 1327ms | 32604kb | C++20 | 4.2kb | 2024-11-16 10:35:43 | 2024-11-16 10:35:44 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#ifdef CPH
#include "/home/floze3/OI/debug.hpp"
#else
#include "/home/floze3/OI/debug_colored.hpp"
#endif
#else
#define debug(...) 42
#define debugArr(...) 42
#define look_time 42
#define look_memory 42
#endif
#define mp(x, y) std::make_pair(x, y)
#define mt std::make_tuple
#define eb emplace_back
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define file(name) \
freopen(name ".in", "r", stdin); \
freopen(name ".out", "w", stdout);
#define fs(x) std::fixed << std::setprecision(x)
#define il inline
#define Avada_Kedavra return 0
#define _IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr), std::cout.tie(nullptr)
#define RANDOM_SEED std::chrono::steady_clock::now().time_since_epoch().count()
#define multitask \
int _; rd >> _; \
while (_--)
using std::cerr;
namespace TYPEDEF {
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using i128 = __int128;
using pii = std::pair<int, int>;
using pi64 = std::pair<i64, i64>;
using vi = std::vector<int>;
using vi64 = std::vector<i64>;
using vu64 = std::vector<u64>;
using vpii = std::vector<pii>;
using vpi64 = std::vector<pi64>;
using si = std::stack<int>;
using si64 = std::stack<i64>;
using su64 = std::stack<u64>;
using spii = std::stack<pii>;
using spi64 = std::stack<pi64>;
using qi = std::queue<int>;
using qi64 = std::queue<i64>;
using qu64 = std::queue<u64>;
using qpii = std::queue<pii>;
using qpi64 = std::queue<pi64>;
using siset = std::set<int>;
using si64set = std::set<i64>;
using su64set = std::set<u64>;
using spiiset = std::set<pii>;
using spi64set = std::set<pi64>;
using str = std::string;
using vstr = std::vector<str>;
using f64 = long double;
} // namespaec TYPEDEF
using namespace TYPEDEF;
/*===============================ALGOS===============================*/
namespace basic_algorithm {
template <typename T> il T abs(T a) { return a >= 0 ? a : -a; }
template <typename T> il void chmin(T &a, T b) { if (a > b) a = b; }
template <typename T> il void chmax(T &a, T b) { if (a < b) a = b; }
template <typename T> il T lowbit(T x) { return (x & (-x)); }
il int pct(int x) { return __builtin_popcount(x); }
il int pct(u32 x) { return __builtin_popcount(x); }
il int pct(i64 x) { return __builtin_popcountll(x); }
il int pct(u64 x) { return __builtin_popcountll(x); }
} // namespace basic_algorithm
using namespace basic_algorithm;
/*================================END================================*/
constexpr int N = 1e6 + 5;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr i64 inf64 = 0x3f3f3f3f3f3f3f3fll;
constexpr f64 eps = 1e-12;
std::mt19937 rng(RANDOM_SEED);
bool mst;
f64 f, ans, s[N];
int n, pos[N], id = -1;
char c[N];
std::pair<f64, int> pr[N];
bool med;
signed main() {
_IOS;
int _; std::cin >> _;
for (int testid = 1; testid <= _; ++testid) {
std::cin >> n >> f >> c, id = n + 1;
// cerr << strlen(c) << '\n';
for (int i = 1; i <= n; ++i) {
s[i] = c[i - 1] - '0';
s[i] -= f;
s[i] += s[i - 1];
// cerr << s[i] << ' ';
}
// cerr << '\n';
for (int i = 1; i <= n; ++i) pr[i] = mp(s[i], i);
pr[++n] = mp(0.0, 0);
std::sort(pr + 1, pr + 1 + n);
f64 res = 1e18;
// for (int i = 1; i < n; ++i)
// chmin(res, abs((pr[i].fi - pr[i + 1].fi) / (pr[i].se - pr[i + 1].se)));
for (int i = 1; i < n; ++i) {
if (abs(res - abs((pr[i].fi - pr[i + 1].fi) / (pr[i].se - pr[i + 1].se))) > eps) {
if (res > abs((pr[i].fi - pr[i + 1].fi) / (pr[i].se - pr[i + 1].se))) {
res = abs((pr[i].fi - pr[i + 1].fi) / (pr[i].se - pr[i + 1].se));
id = std::min(pr[i].se, pr[i + 1].se);
}
}
if (abs(res - abs((pr[i].fi - pr[i + 1].fi) / (pr[i].se - pr[i + 1].se))) < eps) {
chmin(id, std::min(pr[i].se, pr[i + 1].se));
}
}
std::cout << "Case #" << testid << ": " << id << '\n';
}
Avada_Kedavra;
}
/*
all the things you do
the words you say
it all comes back to you
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 8012kb
input:
100 10 0.827672 0010101011 4 0.932623 0100 1000 0.834002 011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...
output:
Case #1: 6 Case #2: 1 Case #3: 10 Case #4: 0 Case #5: 0 Case #6: 1 Case #7: 0 Case #8: 0 Case #9: 0 Case #10: 0 Case #11: 0 Case #12: 4 Case #13: 5 Case #14: 564 Case #15: 0 Case #16: 0 Case #17: 0 Case #18: 0 Case #19: 0 Case #20: 0 Case #21: 0 Case #22: 0 Case #23: 0 Case #24: 844 Case #25: 0 Case...
result:
ok 100 lines
Subtask #2:
score: 22
Accepted
Test #2:
score: 22
Accepted
time: 1327ms
memory: 32604kb
input:
100 15 0.333333 000000000011000 10 0.418754 0101100001 2 0.499999 01 3 0.977951 001 2 0.249999 01 10 0.670229 0111011001 1000 0.500001 001101111110110010110000010010110001110010001101110111010011000010100011011101010110011011011010111110011100011000001000101011100011010100101101111110100101011010111...
output:
Case #1: 6 Case #2: 0 Case #3: 0 Case #4: 2 Case #5: 0 Case #6: 0 Case #7: 0 Case #8: 0 Case #9: 0 Case #10: 0 Case #11: 0 Case #12: 0 Case #13: 0 Case #14: 0 Case #15: 0 Case #16: 4333 Case #17: 0 Case #18: 0 Case #19: 123 Case #20: 0 Case #21: 0 Case #22: 0 Case #23: 0 Case #24: 0 Case #25: 0 Case...
result:
ok 100 lines
Extra Test:
score: 0
Extra Test Passed