QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#752954#5983. Pretty Good ProportionFloze327 ✓1327ms32604kbC++204.2kb2024-11-16 10:35:432024-11-16 10:35:44

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 10:35:44]
  • 评测
  • 测评结果:27
  • 用时:1327ms
  • 内存:32604kb
  • [2024-11-16 10:35:43]
  • 提交

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