#include <iostream>
using namespace std;

/// A BST...
struct Node
{
    double data;
    struct Node *left, *right;
};
///function to create new Node in BST
struct Node *newNode(double item)
{
    struct Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
///function to insert a new Node
/// with given key in BST
struct Node* insert(struct Node *node, double key)
{
    ///if tree is empty, return a new node
    if(node==NULL)
        return newNode(key);
    ///otherwise, recur down the tree..
    if(key <node->data)
        node->left = insert(node->left, key);
    else if (key >node->data)
        node->right = insert(node->right, key);

    return node;
};

double counNodes(struct Node *root)
{
    struct Node *current, *pre;

    double count = 0;
    if(root==NULL)
        return count;

    current=root;
    while(current!=NULL)
    {
        if(current->left==NULL)
        {
            count++;
            current=current->right;
        }
        else
        {
            pre = current->left;
            while(pre->right !=NULL &&
                  pre->right !=current)
                    pre = pre->right;
            if(pre->right==NULL)
            {
                pre->right=current;
                current = current->left;
            }
            else
            {
                pre->right = NULL;

                count++;
                current = current->right;
            }
        }
    }

    return count;
}

///Function to find median in o(n) time and O(1) space...
double findMedian(struct Node *root)
{
    if(root == NULL)
        return 0;

    int count = counNodes(root);
    int currCount = 0;
    struct Node *current = root, *pre, *prev;

    while (current!= NULL)
    {
        if(current->left == NULL)
        {
            currCount++;
            ///odd case..
            if(count %2 !=0 && currCount == (count+1)/2)
                return prev->data;
            ///Even case...
            else if(count%2==0 && currCount == (count/2)+1)
                return (prev->data + current->data)/2;

           ///Update prev..for even no. of nodes...
           prev = current;

           current = current->right;
        }
        else
        {
            ///Find inorder predecessor of current...
            pre = current->left;
            while(pre->right!= NULL && pre->right!=current)
                pre = pre->right;
            /// make current as right child of in. pre.dec.
            if(pre->right == NULL)
            {
                pre->right = current;
                current = current->left;
            }
            /// revert the changes.. made in if part
            /// to restore the original tree.. , fix the right chid of predecessor...

            else
            {
                pre->right = NULL;
                prev = pre;

                currCount++;

                if(count%2!=0 && currCount == (count+1)/2)
                    return current->data;
                else if (count%2!=0 && currCount == (count/2)+1)
                    return (prev->data+current->data)/2;
                ///Update...for even case...

                prev = current;
                current = current->right;
            }
        }
    }
}

int main()
{
    struct Node *root = NULL;
    int n;
    double x;
    cin >> n;
    cin >> x;
    root = insert(root, x);
    for(int i=1; i<n; i++)
    {
        cin >> x;
            insert(root, x);
    }
    //cout << findMedian(root);
    //if(n%2==0)
        printf("%.1f", findMedian(root));

}

if your store data in array of pairs begin loop from zero i=0 not from 1!

[deleted]

Edited by author 21.05.2019 23:17

Online tests surely contain several tests in one file, so:

1. Be sure clean your dictionaries before every test.
2. Be sure read ALL lines of current test, even you got correct answer before all input was used.

This two issues were the reason of my WA1. After fixing them I got "Accepted".

Use the following test to validate mentioned above points:

100
5
5 6 odd
7 8 odd
1 6 even
1 4 odd
7 8 even
3
3
1 1 odd
3 3 odd
1 3 odd
5
4
1 2 even
4 5 even
1 5 odd
3 3 even
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
20
8
1 9 odd
10 17 odd
18 26 odd
4 5 odd
27 40 even
21 40 odd
1 20 odd
10 20 odd
200
8
1 9 odd
10 17 odd
18 26 odd
4 5 odd
27 40 even
21 40 odd
1 20 odd
10 20 odd
-1
Answer:
4
3
3
3
2
6

Спасибо парню из предыдущей ветки,лично мне это реально помогло
Короче смысл в том,что в 7 тесте либо координаты A совпадают с координатами какой-нибудь станции (или тоже самое с B),либо у нескольких станций одинаковые координаты.

Ну и прикол в том,что если вы строите матрицу смежности,то он будет считать что там нет пути, 0 же стоит

the main difficulty here was to understand that you need to use <string>
#include <iostream>
#include <string>
using namespace std;
int main() {
    int n; string arr[4] = { "16", "06", "68", "88" };
    cin >> n;
    if (n <= 4)
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
    else
        cout << "Glupenky Pierre";
}

Judjes tell me after you read my message, I will delete
an AC program.

Here is th 1st program it got WA#3:

[Program was deleted by author, beacuse it got AC =)]
[Thx Vladimir! Judges if you need it, I can post it.]


Here is 2nd program it got AC:

[Program was deleted by author]
[Judges if you need it, I can post that code for a while]

Here is one test:
318 330

Correct answer is 323 (Triviality(323)=0.114551)
AC programs answer for this tests was :
324 (Triviality(324)=1.619195)

It means that AC program gave incorrect answer, but
program which got WA#3 gave correct answer!!!
It's shameful!!!

Edited by author 20.01.2006 20:49

Edited by author 21.01.2006 02:45

Why is triviality(1)=1?

What is the test #11?Give,please......

I am using DP, it works for all TC on discussion. what could be wrong?

print([None, 10, 10, 100, 670, 6700, 55252, 552520, 4816030, 48160300][int(input())])

Hello. How can I find the input values for Test 7? It says that I have a wrong answer there.

#include <iostream>
#include <cmath>
using namespace std;
int fac(int n){
    if (n==0){
        return 1;
    }
    else {
        return n*fac(n-1);
    }
}
int wtf(int n,int k){
    return fac(n)/fac(n-k);
}
int cock(int n){
    int sum;
    for (int i=2;i<=n;i++){
        sum += wtf(n,i);
    }
    return sum;
}
int main()
{
    int n;
    cin >> n;
    cout << cock(n);
    return 0;
}

thanks

Hey,could you help me?

1 1 1
2 2 11
2 4 2
3 3 111
3 5 12
3 9 3
4 4 1111
4 6 112
4 8 22
4 10 13
4 16 4
5 5 11111
5 7 1112
5 9 122
5 11 113
5 13 23
5 17 14
5 25 5
6 6 111111
6 8 11112
6 10 1122
6 12 222
6 14 123
6 18 33
6 20 24
6 26 15
6 36 6

I have no ideas...
Please, give me some tests!

Try below test (TWO edges between the first and the last vertices):

2 2
1 2 60 60
1 2 50 51
1

Answer:
0.000000 1
1


Edited by author 21.12.2018 01:56

Edited by author 05.06.2020 17:42

I can solve it by breadth-first search with Execution time:0.218, but how to solve it with Execution time:0.015 or 0.031??? I have no idea about it. Give me please idea or algorithm's  name to solve it so fast. thank you!