binsearch + dijkstra works but with naive dijkstra

ceils cant be negative

Edited by author 26.05.2024 06:13

These are some of the things I had to overcome:
1)Testing on something like:
6
5 5 1 1 2 2
and
6
5 5 1 1 1 2

2)There cant be 2 out of place pairs in the ascending/descending order

3)Swapping elements across all pairs

Hope this helps someone.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int x1, y1, x2, y2, x0, y0, l;

    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x0 >> y0 >> l;
    cout << fixed << setprecision(2); // <|ENG: Set 2 symbols after dot |> <|RUS: stavim 2 simvola dlia tochki |>
    //<|ENG: get all sides |>
    //<|RUS: poluchaem vse storonui |>
    double firstEdge = sqrt(pow(x1 - x0, 2) + pow(y1 - y0, 2));
    double secondEdge = sqrt(pow(x2 - x0, 2) + pow(y2 - y0, 2));
    double field = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
    double ans2 = max(firstEdge, secondEdge) - l; // <|ENG: Second answer - max length |> <|RUS: Vtoroi otvet = prosto maximum do krainih tochek |>

    double ans1;
    //<|ENG: get the squares of the sides|>
    //<|RUS: Vosvodim v kvadrat storonui |>
    double a = firstEdge * firstEdge;
    double b = secondEdge * secondEdge;
    double c = field * field;
    //<|ENG: checking if there are obtuse angles on the side that is the pineapple field |>
    //<|RUS: Proverka est li typie ygli vosle toi storoni kotoraiy iavliaetsia polem c ananasami |>
    if (a+c < b || b+c < a) {
        ans1 = min(firstEdge, secondEdge) - l;
    }
    else {
        //<|ENG: get half the perimeter of triangle|>
        //<|RUS: poluchaem poly perimetr treygolnika |>
        double p = (firstEdge + secondEdge + field) / 2;
        //<|ENG: get square of triangle|>
        //<|RUS: poluchaem ploshad treygolnika |>
        double S = sqrt(p * (p - firstEdge) * (p - secondEdge) * (p - field));

        //<|ENG: If the area is zero and the field with pineapples does not exist (test: 2 2 2 2 3 3 1)|>
        //<|RUS: Esli ploshad ravna 0 i polia c ananasami kak bu net (test: 2 2 2 2 3 3 1)|>
        if (S == 0 && field == 0) {
            ans1 = min(firstEdge, secondEdge) - l;
        }
        //<|ENG: If the area is zero and more than one side is not zero (test: -5 0 5 0 1 0 1)|>
        //<|RUS: Esli ploshad ravna 0 i ni odna storona ne ravna 0 (test:  -5 0 5 0 1 0 1)|>
        else if (S == 0 && firstEdge != 0 && secondEdge != 0 && field != 0) {
            ans1 =  0;
        }
        else {
            //<|ENG: Default. We just look for the height using the formula|>
            //<|RUS: Obichni slychai. Prosto po formule S = a*h/2 (test:  -5 0 5 0 1 0 1)|>
            double d = 2 * S / field;
            ans1 = d - l;
        }
    }
    //<|ENG: If, after subtracting the rope, the length becomes negative, then do 0|>
    //<|RUS: Esli sle vichetania verevki otvet stal menihe nylia to delayem 0|>
    ans1 = ans1 < 0 ? 0 : ans1;
    ans2 = ans2 < 0 ? 0 : ans2;

    //<|ENG: Next just cout "round(ans1 * 100) / 100" and "round(ans2 * 100) / 100"|>
    //<|RUS: Teper prosto vivedi "round(ans1 * 100) / 100" i "round(ans2 * 100) / 100"|>

    //!!!!!!!!!!!!!!!!!!!
    //cout << round(ans1 * 100) / 100 << endl;
    //cout << round(ans2 * 100) / 100;
    return 0;

    //<|ENG: Thanks a lot for your time here!|>
    //<|RUS: Spasibo chto pochitali i uia vam pomog (navernoe)|>
    // :)
}

Admins, please increase Memory Limit in this task.
It is wrong that solutions with O(Q*log2(10^9)) memory - segment tree on hash table - has not got any chance to pass Memory Limit without additional input queries coordinates compression (because 100000 * 30 * (3*double + char) is obviously > 64 Mb).

This data structure is quite complex even without input queries coordinates compression, why not to AC such solutions? Nowadays commonly used ML is 256 Mb, not 64.

Edited by author 19.05.2024 12:37

Edited by author 19.05.2024 12:39

There is only one eligible lowered numbered ball at any round. Keeping track of this should result in O(n) solution

Write down the sequence, on paper, by hand.
Now, right down the index of each digit on the sequence.
Do you know prefix sums and binary search? It's kinda useful for many problems btw...

Edited by author 15.05.2024 05:54

I solved 1009 and 1012. Now im using new algorithm (log(n)) and program works fast and correct with my tests.

Can you give more tests?

if the cube is at e2, neighbors are:
e1 (near), e3 (far), d2 (left) and f2 (right)

for your convenience
24 orientations of cube:
1 2 3 4 5 6
1 2 4 5 6 3
1 2 5 6 3 4
1 2 6 3 4 5
2 1 3 6 5 4
2 1 4 3 6 5
2 1 5 4 3 6
2 1 6 5 4 3
3 5 1 6 2 4
3 5 2 4 1 6
3 5 4 1 6 2
3 5 6 2 4 1
4 6 1 3 2 5
4 6 2 5 1 3
4 6 3 2 5 1
4 6 5 1 3 2
5 3 1 4 2 6
5 3 2 6 1 4
5 3 4 2 6 1
5 3 6 1 4 2
6 4 1 5 2 3
6 4 2 3 1 5
6 4 3 1 5 2
6 4 5 2 3 1

test:
4
1 4 2 3 6 5
1 4 3 6 5 2
1 4 5 2 3 6
1 4 6 5 2 3
ans:
1
1 2 3 4

:)

For WA12 try this:
9126492316491641269352615215701236589213658621356281376589216562319562396592381659862195621281E-190
100
#

Output must be:
0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009126

What is test #2?

The test contents points entered clockwise, which doesn't respond the condition.
I succeed passing the test only after applied an algo, which is not sesitive to the order of points in polygone

Edited by author 29.04.2024 19:57

Edited by author 29.04.2024 19:57

/* https://acm.timus.ru/problem.aspx?space=1&num=1001 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* #include <sys/queue.h> */
/*
 * Singly-linked List definitions.
 */
#define    SLIST_HEAD(name, type)                        \
struct name {                                \
    struct type *slh_first;    /* first element */            \
}

#define    SLIST_HEAD_INITIALIZER(head)                    \
    { NULL }

#define    SLIST_ENTRY(type)                        \
struct {                                \
    struct type *sle_next;    /* next element */            \
}

/*
 * Singly-linked List functions.
 */
#define    SLIST_INIT(head) do {                        \
    (head)->slh_first = NULL;                    \
} while (/*CONSTCOND*/0)

#define    SLIST_INSERT_AFTER(slistelm, elm, field) do {            \
    (elm)->field.sle_next = (slistelm)->field.sle_next;        \
    (slistelm)->field.sle_next = (elm);                \
} while (/*CONSTCOND*/0)

#define    SLIST_INSERT_HEAD(head, elm, field) do {            \
    (elm)->field.sle_next = (head)->slh_first;            \
    (head)->slh_first = (elm);                    \
} while (/*CONSTCOND*/0)

#define    SLIST_REMOVE_HEAD(head, field) do {                \
    (head)->slh_first = (head)->slh_first->field.sle_next;        \
} while (/*CONSTCOND*/0)

#define    SLIST_REMOVE(head, elm, type, field) do {            \
    if ((head)->slh_first == (elm)) {                \
        SLIST_REMOVE_HEAD((head), field);            \
    }                                \
    else {                                \
        struct type *curelm = (head)->slh_first;        \
        while(curelm->field.sle_next != (elm))            \
            curelm = curelm->field.sle_next;        \
        curelm->field.sle_next =                \
            curelm->field.sle_next->field.sle_next;        \
    }                                \
} while (/*CONSTCOND*/0)

#define    SLIST_FOREACH(var, head, field)                    \
    for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)

/*
 * Singly-linked List access methods.
 */
#define    SLIST_EMPTY(head)    ((head)->slh_first == NULL)
#define    SLIST_FIRST(head)    ((head)->slh_first)
#define    SLIST_NEXT(elm, field)    ((elm)->field.sle_next)

struct num_entry {
    double num;
    SLIST_ENTRY(num_entry) entries;
};
SLIST_HEAD(tq_num, num_entry);

#define my_abs(x) ((x)>0?(x):-(x))

double my_sqrt(double c) {
    double err = 1e-15;
    double t = c;
    if (c < 0) {
        return -1;
    }
    while (my_abs(t- c/t) > err * t) {
        t = (c/t + t) / 2.0;
    }
    return t;
}

int main() {
    struct tq_num head;
    struct num_entry *np;
    unsigned long long m;

    SLIST_INIT(&head);
    /* https://acm.timus.ru/help.aspx?topic=cpp */
    while (scanf("%llu ", &m) != EOF) {
#ifndef ONLINE_JUDGE
        printf("m=%llu\n", m);
#endif
        np = (struct num_entry *)malloc(sizeof(struct num_entry));
        np->num = (double)m;
        SLIST_INSERT_HEAD(&head, np, entries);
    }
    while (!SLIST_EMPTY(&head)) {
        np = SLIST_FIRST(&head);
        printf("%.4f\n", my_sqrt(np->num));
        SLIST_REMOVE(&head, np, num_entry, entries);
        free(np);
    }
    return 0;
}

Edited by author 28.04.2024 12:11