What answer in this case?

Нужно убрать максимальное количество ребёр, но чтобы все вершины имели ненулевую степень.

I thought that stack is the best thing in this case but I've seen 0.015 and 0.001 sec . I've got 0.046

First method:
Use multiple baskets, each basket is a list (in my case, i use vector<int>). Put the date d into the basket numbered d % number_of_baskets. To check the student answer, just pick the basket out and perform binary search. I chose 100 000 as the number of baskets, tried 1 000 000 baskets but it works much worse.

Second method:
Use vector<bool> (not bool array, the later cost 8 times more) to mark numbers under 300 000 000 (actually the vector size can go up to 500 000 000, but for some unknown reason, this smaller size run faster). Create another vector<int> to store the numbers that can't be marked using the bool vector above. Use binary_search to check for existence.

It seem like the IO is bottleneck, I used ios::sync_with_stdio(false) and my program run from ~1.5s to ~0.2s

Edited by author 01.10.2018 12:46

seems I have solved memory problem..  but I don't know if bitset can fit in time

can O(1e8) fit into 1 sec??

Edited by author 27.09.2018 06:21

If you got WA, especially if you got WA9
First line is input string, second is answer

TEST. TEST? TEST! TEST.
Test. Test? Test! Test.

??????????????????????
??????????????????????

!TEST!TEST!
!Test!Test!

A
A

TEST
    TEST
        TEST
Test
    test
        test

TEST     T      TEST
Test     t      test

Also try empty input.

Edited by author 30.09.2018 19:14

This enchanted test 8: I just can not get through it. Maybe there is just that unrepresentable case of "impossible", the emergence of which, under given conditions, I can not even imagine?

I dont understand: when I had swaped 'Impossible' to '0' my program solved more tests than late.

void fallBack(int angle, int M, int curEnergy, int curAmmo);
void advance(int angle, int M, int curEnergy, int curAmmo);
int findX(int curEnergy);

int main()
{
    int curEnergy, curAmmo;
    char behaviour;
    int M, MP, angle;
    int N, NP, offset;
    scanf_s("%i %i", &curEnergy, &curAmmo);
    scanf_s(" %c", &behaviour);
    scanf_s("%i %i %i", &M, &MP, &angle);
    if (behaviour == 'A') {
        scanf_s("%i %i", &N, &NP);
    }
    else if (behaviour == 'P') {
        scanf_s("%i", &offset);
        offset *= -1;

    }
    while (1) {
        switch (behaviour) {
        case 'A':
            if ((N*NP) > (M*MP * 3)) {
                advance(angle, M, curEnergy, curAmmo);
                return 0;
            }
            else {
                fallBack(angle, M, curEnergy, curAmmo);
                return 0;
            }
        case 'D':
            if ((M * 20) >= curAmmo) {
                fallBack(angle, M, curEnergy, curAmmo);
                return 0;
            }
            else {
                behaviour = 'G';
                break;
            }
        case 'G':
            if (M == 0) {
                printf("STOP");
            }
            if (abs(angle) < 5) {
                int P = (int)fmin(20, curAmmo);
                printf("FIRE %i", P);
                return 0;
            }
            else if (angle >= 5) {
                printf("LEFT %i", findX(curEnergy));
                return 0;
            }
            else if (angle <= -5) {

                printf("RIGHT %i", findX(curEnergy));
                return 0;
            }
        case 'P':
            if (M != 0) {
                behaviour = 'D';
                break;
            }
            else {
                if (offset >= -180 && offset <= -160) {
                    printf("BACKWARD %i", findX(curEnergy));
                    return 0;
                }
                else if (offset > -160 && offset < -90) {
                    printf("RIGHT %i", findX(curEnergy));
                    return 0;
                }
                else if (offset >= -90 && offset < -20) {
                    printf("LEFT %i", findX(curEnergy));
                    return 0;
                }
                else if (offset >= -20 && offset <= 20) {
                    printf("FRONT %i", findX(curEnergy));
                    return 0;
                }
                else if (offset > 20 && offset <= 90) {
                    printf("RIGHT %i", findX(curEnergy));
                    return 0;
                }
                else if (offset > 90 && offset < 160) {
                    printf("LEFT %i", findX(curEnergy));
                    return 0;
                }
                else if (offset >= 160 && offset <= 180) {
                    printf("BACKWARD %i", findX(curEnergy));
                    return 0;
                }
            }
        }
    }


    return 0;
}

void fallBack(int angle, int M, int curEnergy, int curAmmo)
{
    if (abs(angle) >= 5 || M == 0) {
        printf("BACKWARD %i", findX(curEnergy));
    }
    else {
        int P = (int)fmin(20, curAmmo);
        printf("FIRE %i", P);
    }
}
void advance(int angle, int M, int curEnergy, int curAmmo)
{
    if (abs(angle) >= 10 || M == 0) {
        printf("FRONT %i", findX(curEnergy));
    }
    else {
        int P = (int)fmin(20, curAmmo);
        printf("FIRE %i", P);
    }
}
int findX(int curEnergy)
{
    int X;
    if (curEnergy > 100) {
        X = 100;
    }
    else {
        X = curEnergy;
    }
    return X;
}

Event simple A+B get's around 900KB for me, but I've seen some ACs with 400KB in Java 1.8. Can you tell me how?

O(n+m) solution exists: extend <https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm> to keep not only the top of each set in the disjoint-set forest, but also the weight of the path till that top.

Write code that way:

    if(n>=1000)
        puts("legion");
    else if (n>=500)
        puts("zounds");
    else if (n>=250)
        puts("swarm");
    else if (n>=100)
        puts("throng");
    else if (n>=50)
        puts("horde");
    else if (n>=20)
        puts("lots");
    else if (n>=10)
        puts("pack");
    else if (n>=5)
        puts("several");
    else puts("few");

use printf and scanf instead of cin,cout;

a=[]
for i in range(int(input())):
    c=str(input())
    if len(a)==0 :
        a.append(c)
        continue
    d=(a[0].split())[1]
    d=int(d)
    k=int((c.split())[1])

    if k>=d :
        a.reverse()
        a.append(c)
        a.reverse()
    else:
        for j in range (len(a)):
            h=int((a[j].split())[1])



            if k >= h:
                p = a[:j]
                o = a[j:]
                p.append(c)
                p.extend(o)








for i in range(len(a)):
   print(a[i])


Edited by author 26.09.2018 20:38

the number of integer point inside circle  is sigma(r*r/(4*i+1)-r*r/(4*i+3))
use stern borcot to cut hyperbola curve it can be done O(r^(2/3))

int main()
{
    optimize();
    int n,k;
    cin>>n>>k;
    k--;
    int z=k;
    bool b=0;
    int a[n+10];
    for(int i=0;i<n;i++)
    {
        if(k!=0)
        {
            if(b==0)
            {
                a[i]=k;
                b=1;
                z--;
            }
            else
            {
                if(z==0)
                {
                    a[i]=0;
                    k=0;
                    b=1;
                    continue;
                }
                a[i]=-k;
                k--;
                b=0;
                z--;
                if(z==0)
                    k=0;
            }
        }
        else
            a[i]=0;
    //dbg(z);
    }
    for(int i=n-1;i>=0;i--)
        cout<<a[i]<<" ";
    //return main();
}

when going to print 0 0 -3 3  or  -3 3 0 0 I am getting WA..But When I print 0 0 -1 1 I get AC..Why?what is the difference between 1st two case and last one??Can anyone explain me??

Thanks to Oleksandr Kulkov for preparing!