Читаю который раз, а все понять не могу, что за бред...
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.

why WA10?

please, give me some test
all test posted here is working

i tried to solve this problem about 50 times
help me!!!!!!!!

Any ideas?

SUJE-MI PULA

Please help me.. What's wrong in this code?


#include <stdio.h>
#include <math.h>

#define MAX_COUNT 100
#define PI 2. * acos (0.)


struct vertices
{
  double x;
  double y;
};

double solve (struct vertices *vert, int n, double r);

int main ()
{
  struct vertices vert[MAX_COUNT];
  double r;
  double res;
  int n;
  int i;

  if (scanf ("%d", &n) != 1)
    return -1;
  if (n < 1 || n > MAX_COUNT)
    return -2;

  if (scanf ("%lg", &r) != 1)
    return -3;
  if (r < 0.)
    return -4;

  for (i = 0; i < n; i++){
    if (scanf ("%lg %lg", &vert[i].x, &vert[i].y) != 2)
      return -5;
    if (fabs (vert[i].x) > 101. || fabs (vert[i].y) > 101.)
      return -6;
  }

  res = solve (vert, n, r);

  res = (double)((int)(res * 100));
  res /= 100;

  printf ("%.2lf\n", res);

  return 0;
}

double solve (struct vertices *vert, int n, double r)
{
  double res = 0.;
  double abs_x, abs_y;
  int i, t;

  for (i = 0; i < n; i++){
    t = (i + 1) % n;
    abs_x = (vert[i].x - vert[t].x) * (vert[i].x - vert[t].x);
    abs_y = (vert[i].y - vert[t].y) * (vert[i].y - vert[t].y);
    res += sqrt (abs_x + abs_y);
  }

  res += r * PI * 2.;

  return res;
}

My solution uses simple Floyd algo.It passed all tests on this board, but still gets WA.

Edited by author 02.04.2009 12:58

Объясните по русски, что им надо???