oj.uz

Submission #739938

# Submission time Handle Problem Language Result Execution time Memory
739938 2023-05-11T17:19:18 Z danikoynov Parking (CEOI22_parking) C++14
10 / 100
 2000 ms 3200 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;
int n, m, t[maxn][2];
vector < pair < int, int > > path, ans;
int found = -1;

void brute()
{
    /**cout << "here " << path.size() << endl;
    for (int i = 1; i <= m; i ++)
        cout << t[i][0] << " " << t[i][1] << endl;*/
    bool done = true;
    for (int i = 1; i <= m; i ++)
    {
        if (t[i][0] != t[i][1])
        {
            done = false;
            break;
        }
    }

    if (done)
    {
        ///cout << "done" << endl;
        if (found == -1 || path.size() < ans.size())
            ans = path, found = 1;
        return;
    }

    if (path.size() >= ans.size() && found != -1)
        return;

    for (int i = 1; i <= m; i ++)
    {
        if (t[i][0] == t[i][1])
            continue;
        if (t[i][0] == 0)
            continue;
        if (t[i][1] == 0)
        {
            for (int j = 1; j <= m; j ++)
            {
                if (i == j)
                    continue;

                if (t[j][1] == 0 && t[j][0] == t[i][0])
                {
                    path.push_back({i, j});
                    t[j][1] = t[j][0];
                    t[i][0] = 0;
                    brute();
                    path.pop_back();
                    t[j][1] = 0;
                    t[i][0] = t[j][0];
                }
            }
        }
        else
        {

        for (int j = 1; j <= m; j ++)
        {
            if (j == i)
                continue;
            if (t[j][0] == 0)
            {
                path.push_back({i, j});
                t[j][0] = t[i][1];
                t[i][1] = 0;
                brute();
                t[i][1] = t[j][0];
                t[j][0] = 0;
                path.pop_back();
            }
            else
            if (t[j][1] == 0 && t[j][0] == t[i][1])
            {
                t[j][1] = t[i][1];
                t[i][1] = 0;
                path.push_back({i, j});
                brute();
                path.pop_back();
                t[i][1] = t[j][1];
                t[j][1] = 0;
            }
        }
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> t[i][0] >> t[i][1];
    }

    brute();
    if (found == -1)
    {
        cout << -1 << endl;
        return;
    }
    cout << ans.size() << endl;
    for (pair < int, int > cur : ans)
        cout << cur.first << " " << cur.second << endl;
}

int main()
{
    solve();
    return 0;
}
/**
1 2
1 0
1 0
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 3200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 2079 ms 3200 KB Time limit exceeded
12 Halted 0 ms 0 KB -