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