3 6
1 2
2 3
3 1
4 5
5 6
6 4

Try
7 10
1 2
1 3
1 4
5 6
5 7
8 9
8 10
8 11
12 13
12 14
This test changed my solution totally. Hope it helps you:)

3 4
1 2
1 3
4 5
4 6
ans:
1 5 6
2 3 4

Edited by author 03.09.2019 09:23

Many people has already written about it, but... I really don't understand why I get WA. My program pass all tests here. Please, help to find bug.
--

Edited by author 29.07.2016 15:52

Hi! My code has complexity O(2^N) and it had AC in 0.001 sec. A friend of mine noted this: when I run my program in this case:

50 50
1 2
3 4
5 6
... Same pattern here
95 96
97 98
99 100

And it will give TLE.

Please, add this case!

50 50
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100

I've tested all inputs from other themes, but still got wa in 3rd. Help, please!
The algorithm based on the half-invariant idea.

#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;


int main(){
    int n, m;
    cin >> n >> m;
    bool **e = new bool*[2*n];
    for (int i=0; i<2*n; i++){
        e[i] = new bool[2*n];
        for (int j=0; j<2*n; j++){
            e[i][j] = false;
        }
    }
    int v1, v2;
    for (int i=0; i<m; i++){
        cin >> v1 >> v2;
        int tmp;
        if (v1 > v2){
            tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
        e[v1-1][v2-1] = true;
        e[v2-1][v1-1] = true;
    }
    int inv=0;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (e[i][j]) inv++;
            if (e[n+i][n+j]) inv++;
        }
    }
    int *t =new int[2*n];
    for (int i=0; i<2*n; i++){
        t[i] = i;
    }
    while (inv > 0){
        int s = 0;
        for (int i=0; i<n; i++){
            int i_out = 0;
            int i_in = 0;
            for (int k=0; k<n; k++){
                if (e[t[i]][t[k]] || e[t[k]][t[i]]){
                    i_in++;
                }
                if (e[t[i]][t[k+n]] || e[t[k+n]][t[i]]){
                    i_out++;
                }
            }
            for (int j=n; j<2*n; j++){
                int j_out = 0;
                int j_in = 0;
                for (int k=0; k<n; k++){
                    if (e[t[k+n]][t[j]] || e[t[j]][t[k+n]]){
                        j_in++;
                    }
                    if (e[t[k]][t[j]] || e[t[j]][t[k]]){
                        j_out++;
                    }
                }
                if (e[t[i]][t[j]] || e[t[j]][t[i]]){
                    j_out--;
                    j_out--;
                }
                if (i_in + j_in > i_out + j_out){
                    s++;
                    inv -= (i_in + j_in - i_out - j_out);
                    int tmp = t[i];
                    t[i] = t[j];
                    t[j] = tmp;
                }
                if (s == 1) break;
            }
            if (s == 1) break;
        }
        if (s == 0){
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    string tour1, tour2;
    tour1 = "";
    tour2 = "";
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (t[i]>t[j]){
                int tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
            }
            if (t[i+n]>t[j+n]){
                int tmp = t[i+n];
                t[i+n] = t[j+n];
                t[j+n] = tmp;
            }
        }
    }
    for (int i=0; i<n; i++){
        std::ostringstream ostr;
        ostr << (t[i]+1);
        std::string theNumberString = ostr.str();
        tour1 = tour1 + theNumberString + " ";
    }
    for (int i=0; i<n; i++){
        std::ostringstream ostr;
        ostr << (t[n+i]+1);
        std::string theNumberString = ostr.str();
        tour2 = tour2 + theNumberString + " ";
    }
    cout << tour1 << endl << tour2 << endl;
    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

if you use brute search and got TLE then try to sort the input. :-D

#include<stdio.h>
#include<iostream>

using namespace std;
int a,b,n,m,g[1000][1000];
int _max = -1000;
int main()
{
scanf("%d %d",&n,&m);

for(int i = 1;i<=m;i++)
{

                scanf("%d %d",&a,&b);
                g[a][b]=1;
                g[b][a]=1;
}


for(int k = 1;k<=2*n;k++)
{
        for(int l = 1;l<=2*n;l++)
        {
           if(k==l){continue;}
           else if(g[k][l]==1)
           {
           g[k][l]=2;
           g[k][l]=2;
           }
        }
}

for(int k = 1;k<=2*n;k++)
{
        for(int l = 1;l<=2*n;l++)
        {
           if(k==l){continue;}
           else if(g[k][l]==0)
           {
           g[k][l]=1;
           g[k][l]=1;
           }
        }
}

int key = 0;
for(int k = 1;k<=2*n;k++)
{
        for(int l = 1;l<=2*n;l++)
        {
          if(key>=2){return 0;}
          else if(k==l){continue;}
          else if(g[k][l]==1)
          {
                printf("%d %d\n",k,l);
                key++;
          }
        }

}

printf("IMPOSSIBLE");
}

Very strange... I tried all tests here and they all worked well. It's a DP,right? But I always get wa4. I added this to my code: when I worked out my answer, I'll check them myself. If there are some shouldn't be in the same pair,then while(1). As a result I got TLE4. So it obviously I've made a wrong answer. BUT HOW COULD IT HAPPEN!!!

What test is it?

Please help me! I can't understand why I got WA on third test...

Edited by author 31.05.2008 03:32

What is the test #3

This is my Code:

[code deleted]

Thanks A Lot!!!

Edited by moderator 11.03.2008 13:24

i write program which have wa#1

"But it appeared that among those problems there were some,
which have the analogous solutions."

for me it's very difficult to understand such situation:

solution of problem A is "analogous" to solution of problem B
and solution of problem B is "analogous" to solution of problem C
BUT solution of problem A is NOT "analogous" to solution of problem C

in other words relation "analogous" is not transitive

this fact must be clarified in the problem statement

If you think your algorithm is correct and still got WA , try to use adj-matrix,don't use adj-list

Try this test:

2 1
1 3

answer:

2 3
1 4