QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#219410#5152. Circular Caramel Cookiegramolis#WA 0ms3856kbC++171.5kb2023-10-19 14:25:252023-10-19 14:25:25

Judging History

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

  • [2023-10-19 14:25:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2023-10-19 14:25:25]
  • 提交

answer

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;

const ld EPSILON = 1e-9;

ll can_fit_x_squares(ld x, ld y, ld radius){
    ld d = sqrt(x * x + y * y);
    return d <= radius;
}

ll try_radius(ld radius){
    ll i_radius = ll(radius);
    // for each column find how many rows of waffle we get
    // we calculate ans for (+, +) quarter

    ll cur_squares = 0;
    for(ll i=0;i<=i_radius+1;i++){
        // find max height of stack
        ll l = 0;
        ll r = radius + 1;

        while(r - l >= 10){
            ll mid = (r + l) / 2;
            if(can_fit_x_squares(i + 1, mid, radius)){
                l = mid - 1;
            } else {
                r = mid + 1;
            }
        }
        for(ll y=r;y>=l;y--){
            if(can_fit_x_squares(i + 1, y, radius)){
                cur_squares += y;
                break;
            }
        }
    }
    return cur_squares * 4;
}


// g++ -std=c++17 main.cpp -o main && ./main
// g++-12 -std=c++17 -O2 -Wall -lm main.cpp -o main && ./main
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //ofstream cout ("output.txt");
    //ifstream cin ("input.txt");

    ll s;
    cin >> s;

    ld l = ld(0);
    ld r = sqrt(ld(s));

    while(r - l >= EPSILON) {
        ld mid = (l + r) / ld(2);
        if(try_radius(mid) >= s){
            r = mid;
        } else {
            l = mid;
        }

    }

    cout << fixed << setprecision(9) << l << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

input:

11

output:

2.236067977

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

59

output:

4.999999999

result:

ok found '5.0000000', expected '5.0000000', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3848kb

input:

1

output:

0.999999999

result:

wrong answer 1st numbers differ - expected: '1.4142136', found: '1.0000000', error = '0.2928932'