What does this test look like?

You calculate f2 by this formula: f2 = f1 + f0
f2 may be small enough to be stored by an integer, but f1 and f0 may be very large.
For example:
1 = (-2935892358923598) + (2935892358923599)

Hello
what's compiler is on the server? where is my typeof() ?

I use sqrt decomposition and some DP.
My DP idea is to keep for each robot the shortest path which we can find if we detour by left or right. And I use sqrt decomposition to find the next encountered robot on the current path.
Could someone give me a tricky example?

Edit: I wrote the update of the sqrt decomposition again(different) and now I get WA23.

Edited by author 22.09.2010 15:13

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int a[501][3], f[501], trace[501], n, ans, t;

void sort(int l, int r) {
    int x = a[(l + r) >> 1][0];
    int i, j, t[3];
    i = l;
    j = r;
    do {
        while (a[i][0] < x)
            i++;
        while (a[j][0] > x)
            j--;
        if (i <= j) {
            memcpy(t, a[i], sizeof(t));
            memcpy(a[i], a[j], sizeof(t));
            memcpy(a[j], t, sizeof(t));
        }
        i++;
        j--;
    } while (i <= j);
    if (i < r)
        sort(i, r);
    if (l < j)
        sort(l, j);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        a[i][2] = i;
    }
    for (int i = 1; i <= n; i++)
        f[i] = 1;
    sort(1, n);
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            if ((a[j][0] < a[i][0]) && (a[j][1] > a[i][1]) && (f[j] + 1 > f[i])) {
                f[i] = f[j] + 1;
                trace[i] = j;
            }
    ans = 0;
    t = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] > ans) {
            ans = f[i];
            t = i;
        };
    printf("%d\n", ans);
    while (t != 0) {
        printf("%d ", a[t][2]);
        t = trace[t];
    }
    return 0;
}

Читаю который раз, а все понять не могу, что за бред...
I read which time, and all I can not understand that for delirium...

What it can be???i have TL 15 if i change code i have wa 15 it's terrible)

5+5+13+14=37
27+8=35
result=2

of course you need O(n) and I had it but
I was mad about this(TLE), but I thought a little and tried to use
char s[200010]
and now
AC 0.031))))))))))))))
don't use list or string in this problem
write your own implementation of std::list
good luck)

Edited by author 10.07.2009 23:29

Edited by author 10.07.2009 23:49

why my answer of the test#1 is incorrect?
codenames
grille
keywords
mnemonic
playgame
random
rectangle
rejudge
shaitan
size
twosides

we can easily design 1000 stacks using a linked list，every node we 'll use a int to store its data，another int to store its father's index，we'll use 8 byte each node, about 800K,that will get MLE.

Then we can see the index of a node's father will always <=100000,we can just use 17 bit to store it,instead of a int(32 bit),zipped it and get AC~ :)

Why WA on test1.
I think this is rigth.

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
    int n,max = 1,summa, temp;
    int *w;
    cin >> n;
    w = new int[n];
    for(int i = 0; i < n; i++)
    {
        max *= 2;
        cin >> w[i];
    }
    max -= 2;
    bitset<20> a;
    temp = w[0];
    while(max >= 1)
    {
        a = max;
        summa = 0;
        for(int i = 0; i < n; i++)
        {
            if(a.at(i))
                summa += w[i];
            else
                summa -= w[i];
        }
        if(temp > summa && summa >= 0)
            temp = summa;
        max--;
    }
    cout << temp;
    return 0;
}

I tried all tests given here (also in other forum messages) and always get correct answer. I have no idea, what's wrong with this:

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

class Task
{
public:
    int arrSameTasks[101], lastIndex;
    bool IsInTour;

    Task() { IsInTour = false; lastIndex = 0; }

    void AddSameTask(int someTask)
    {
        lastIndex++;
        arrSameTasks[lastIndex] = someTask;
    }

    void Show()
    {
        for (int i = 1; i <= lastIndex; i++)
            cout << arrSameTasks[i] << " ";
        cout << endl;
    }

    bool SameTasksFounded(int arrToCheck[], int n)
    {
        for (int i = 1; i <= lastIndex; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (arrSameTasks[i] == arrToCheck[j])
                    return true;
            }
        }
        return false;
    }
};

class TempTours     // промежуточные расположения задач в турах
{
public:
    TempTours() {}
    int tempTour1[101], tempTour2[101], tempIndex1, tempIndex2;

    void CreateData(int tour1[], int tour2[], int index1, int index2)
    {
        for (int i = 1; i <= index1; i++)
            tempTour1[i] = tour1[i];
        for (int i = 1; i <= index2; i++)
            tempTour2[i] = tour2[i];
        tempIndex1 = index1;
        tempIndex2 = index2;
    }

    int IndDifference()
    { return abs (tempIndex1 - tempIndex2);    }

    void Show()
    {
        cout << "\ntempTour1:\n";
        for (int i = 1; i <= tempIndex1; i++)
            cout << tempTour1[i] << " ";
        cout << "\ntempTour2:\n";
        for (int i = 1; i <= tempIndex2; i++)
            cout << tempTour2[i] << " ";
    }
};




bool MakeArrays(Task allTasks[], int n, int tour1[], int tour2[], int &index1, int &index2,
                int freeTasks[], int &indexFree)
{
    bool ListsChanged;  // будем проверять, сделаны ли изменения в списках туров
    for (;;)
    {
        indexFree = 1;
        ListsChanged = false;

        for (int i = 1; i <= 2*n; i++)
        {
            if (!(allTasks[i].IsInTour))   // поиск первой свободной задачи
            {
                if (!(allTasks[i].SameTasksFounded(tour1, index1)))  // если в 1-ом туре не найдено подобных задач,...
                {   // ...а во 2-ом туре такие есть или число задач в командах сейчас равно
                    if (allTasks[i].SameTasksFounded(tour2, index2) || index1 == index2)
                    {
                        if (index1 > n) // а тут мы превысили число задач в одном туре
                        {
                            cout << "IMPOSSIBLE";
                            return false;
                        }
                        tour1[index1] = i; index1++; allTasks[i].IsInTour = true;  // помещаем ее в 1-ый тур
                        ListsChanged = true;
                    }
                    else           // а если нет "врагов" ни там, ни там + индексы не равны
                    {
                        freeTasks[indexFree] = i; indexFree++;
                    }
                }
                else         // если в 1-ом туре есть подобные задачи,...
                {
                    if (!(allTasks[i].SameTasksFounded(tour2, index2)))    // ...а во 2-ом их нету
                    {
                        if (index2 > n) // тут мы опять превысили число задач в одном туре
                        {
                            cout << "IMPOSSIBLE";
                            return false;
                        }
                        tour2[index2] = i; index2++; allTasks[i].IsInTour = true;  // помещаем ее во 2-ой тур
                        ListsChanged = true;
                    }
                    else           // а если "враги" повсюду
                    {
                        cout << "IMPOSSIBLE";
                        return false;
                    }
                }
            }
        }
        if (!ListsChanged)  // наконец, когда списки перестали меняться
            return true;
    }
}

int Max(int arr[], int n)
{
    int max = arr[0], maxIndex = 0;
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
        {
            max = arr[i];
            maxIndex = i;
        }
    return maxIndex;
}


int main()
{
    freopen("input.txt", "r", stdin);

    int n, m;
    cin >> n >> m;

    Task * allTasks = new Task[2*n+1];       // массив всех задач

    int task1, task2;
    for (int i = 1; i <= m; i++)
    {
        cin >> task1 >> task2;
        allTasks[task1].AddSameTask(task2);
        allTasks[task2].AddSameTask(task1);
    }

    /*for (int i = 1; i <= 2*n; i++)
    {
        cout << "Same tasks for task " << i << ": \n";
        allTasks[i].Show();
    }*/

    int tour1[51], tour2[51];         // задачи 1-ого тура, задачи 2-ого тура
    int index1 = 1, index2 = 1;       // индексы, указывающие, куда вставлять очередную задачу

    int freeTasks[101], indexFree = 1;  // здесь будут храниться временно незанятые задачи, у которых на момент проверки не будет "врагов" ни в одном туре

    TempTours * arrTempTours = new TempTours[2*n+1];
    int indexTemp = 0;

    // Проход по всем задачам и генерация временных пар массивов задач
    for (;;)
    {
        indexFree = 1; index1 = 1; index2 = 1;
        if (!MakeArrays(allTasks, n, tour1, tour2, index1, index2, freeTasks, indexFree))
            return 0;

        index1--; index2--;
        arrTempTours[indexTemp].CreateData(tour1, tour2, index1, index2);

        //cout << "\narrTempTours[" << indexTemp << "]:";
        //arrTempTours[indexTemp].Show();

        indexTemp++;
        if (indexFree == 1)
            break;
    }

    indexFree = 1; index1 = 1; index2 = 1;

    int * arrDiff = new int[2*n+1];
    for (int i = 0; i < indexTemp; i++)
        arrDiff[i] = arrTempTours[i].IndDifference();

    for (int i = 0; i < indexTemp; i++)
    {
        int tempInd1 = arrTempTours[Max(arrDiff, indexTemp)].tempIndex1;
        int tempInd2 = arrTempTours[Max(arrDiff, indexTemp)].tempIndex2;
        if (index1 == index2)
        {
            for (int j = index1; j < index1 + tempInd1; j++)
                tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1];
            index1 += tempInd1;
            for (int j = index2; j < index2 + tempInd2; j++)
                tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1];
            index2 += tempInd2;
        }
        else
        {
        if (index1 < index2)
        {
            if (tempInd1 > tempInd2)
            {
                for (int j = index1; j < index1 + tempInd1; j++)
                    tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1];
                index1 += tempInd1;
                for (int j = index2; j < index2 + tempInd2; j++)
                    tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1];
                index2 += tempInd2;
            }
            else
            {
                for (int j = index1; j < index1 + tempInd2; j++)
                    tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index1+1];
                index1 += tempInd2;
                for (int j = index2; j < index2 + tempInd1; j++)
                    tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index2+1];
                index2 += tempInd1;
            }
        }
        else
        {
            if (tempInd1 < tempInd2)
            {
                for (int j = index1; j < index1 + tempInd1; j++)
                    tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1];
                index1 += tempInd1;
                for (int j = index2; j < index2 + tempInd2; j++)
                    tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1];
                index2 += tempInd2;
            }
            else
            {
                for (int j = index1; j < index1 + tempInd2; j++)
                    tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index1+1];
                index1 += tempInd2;
                for (int j = index2; j < index2 + tempInd1; j++)
                    tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index2+1];
                index2 += tempInd1;
            }
        }
        }
        if (index1-1 > n || index2-1 > n)  // переполнение числа задач в одном туре
        {
            cout << "IMPOSSIBLE";
            return 0;
        }

        arrDiff[Max(arrDiff, indexTemp)] = -1;
    }

    for (int i = 1; i <= n; i++)
        cout << tour1[i] << " ";
    cout << "\n";
    for (int i = 1; i <= n; i++)
        cout << tour2[i] << " ";


    return 0;
}


I've been trying to get AC with this program for 2 days and... yes, it's rather big. Somebody, if you've got a heart, please give me test #3! ))

Edited by author 17.09.2010 02:31

The testcases, after rejudgement, are harder than before. So I really wonder if simply randomization could get AC.

I first wrote a program WHOLLY random, and got WA at 4.
Then I added the checking part of my program. When one-round randomization failed, I will start another, and so on. Then I got TLE at 14, 15 or 19 (I have tried about 10 times).
Finally, I realised that I must modify the random part. So I made a improvement: when I try to find the value of one pixel, I will take the PROCESSED pixel which could have the impression on that pixel into consideration. And I will adjust the random argument basing on these infos. This time I got AC.

Wish my method will be helpful.

rt~~~

I had WA 11 and this test helped me:
0 0 0
0 0 10
0 1 168
7
Correct answer is 10.00. In short the problem is that the distance between C and the line between A and B is less then R but still the thread doesn't pass through the ball.

What could be in this test? Can you give me some tests?

I submitted my program to 1079 and get AC.
It at least shows that my ALGO work for small data.

By the way, my answer for 10^18 is
2504730781961
Is it right?

Maybe the 'int64' or some problems like this make me WA.
Could you please tell me why? I am confused.

Thanks in advance.