— Dark mode

COCI 2006/2007 #3

Tenkici

  • Start: 2019-07-24 14:00:00
  • End: 2019-07-24 16:30:00
Submission details
Task:Tenkici
Sender:henrikaalto
Submission time:2019-07-25 18:25:03 +0300
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#10.01 sdetails
#20.01 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails
#110.01 sdetails
#120.01 sdetails
#130.02 sdetails
#140.01 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
using ii=long long;
#define F first
#define S second
int vapaa[501][501];
int main()
{
    int n;
    cin >> n;
    vector<pair<int,int>> orig(n), fin(n);
#define f first
#define s second
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            vapaa[i][j] = 1;
        }
    }
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        orig[i] = {a, b};
        vapaa[a][b] = 0;
    }
    priority_queue<pair<int,int>> pq;
    for (int i = 0; i < n; ++i) {
        pq.emplace(-orig[i].F, i);
    }
    for (int it = 0; it < n; ++it) {
        fin[pq.top().S].F = it;
        pq.pop();
    }
    assert(pq.empty());
    for (int i = 0; i < n; ++i) {
        pq.emplace(-orig[i].S, i);
    }
    for (int it = 0; it < n; ++it) {
        fin[pq.top().S].S = it;
        pq.pop();
    }
    vector<pair<char, int>> moves;
    for (int x = 0; x < n; ++x) {
        for (int i = 0; i < n; ++i) {
            while (orig[i] != fin[i]) {
                if (orig[i].F < fin[i].F && vapaa[orig[i].F + 1][orig[i].S]) {
                    vapaa[orig[i].F][orig[i].S] = 1;
                    orig[i].F++;
                    moves.emplace_back('R', i + 1);
                    vapaa[orig[i].F][orig[i].S] = 0;
                }
                else if (orig[i].F > fin[i].F && vapaa[orig[i].F - 1][orig[i].S]) {
                    vapaa[orig[i].F][orig[i].S] = 1;
                    orig[i].F--;
                    moves.emplace_back('L', i + 1);
                    vapaa[orig[i].F][orig[i].S] = 0;
                }
                else if (orig[i].S < fin[i].S && vapaa[orig[i].F][orig[i].S + 1]) {
                    vapaa[orig[i].F][orig[i].S] = 1;
                    orig[i].S++;
                    moves.emplace_back('D', i + 1);
                    vapaa[orig[i].F][orig[i].S] = 0;
                }
                else if (orig[i].S > fin[i].S && vapaa[orig[i].F][orig[i].S - 1]) {
                    vapaa[orig[i].F][orig[i].S] = 1;
                    orig[i].S--;
                    moves.emplace_back('U', i + 1);
                    vapaa[orig[i].F][orig[i].S] = 0;
                }
                else break;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        assert(orig[i] == fin[i]);
    }
    cout << moves.size() << "\n";
    for (auto [y, x] : moves) {
        cout << x << " " << y << "\n";
    }
}

Test details

Test 1

Verdict:

input
3
2 1
3 1
2 2
view save

correct output
3
1 U
2 R
3 R
view save

user output
3
3 L
3 D
1 D
view save

Test 2

Verdict:

input
4
3 2
3 1
4 1
4 2
view save

correct output
8
2 U
2 U
3 U
1 U
...
view save

user output
8
1 L
1 D
1 D
2 L
...
view save

Test 3

Verdict:

input
5
5 4
4 2
4 4
2 2
...
view save

correct output
6
5 U
5 U
4 U
2 U
...
view save

user output
6
1 D
2 D
3 L
4 L
...
view save

Test 4

Verdict:

input
6
5 1
5 6
1 4
6 6
...
view save

correct output
7
1 U
1 U
6 U
3 D
...
view save

user output
7
1 L
1 D
2 L
2 L
...
view save

Test 5

Verdict:

input
7
5 3
4 4
5 5
3 5
...
view save

correct output
8
6 D
5 U
3 D
7 U
...
view save

user output
8
1 R
3 D
5 L
5 U
...
view save

Test 6

Verdict:

input
8
8 7
2 2
8 8
2 1
...
view save

correct output
16
4 D
2 D
2 D
5 D
...
view save

user output
16
1 U
2 R
2 R
2 D
...
view save

Test 7

Verdict:

input
9
1 2
2 2
8 8
9 8
...
view save

correct output
24
8 D
8 D
2 D
2 D
...
view save

user output
24
1 D
1 R
1 R
1 D
...
Truncated

Test 8

Verdict:

input
10
4 2
5 3
7 1
3 2
...
view save

correct output
36
4 U
4 U
1 U
1 U
...
view save

user output
36
1 D
1 L
1 L
1 D
...
Truncated

Test 9

Verdict:

input
50
1 47
12 29
35 12
6 47
...
view save

correct output
544
34 D
34 D
34 D
34 D
...
view save

user output
544
1 R
1 R
1 R
1 R
...
Truncated

Test 10

Verdict:

input
100
53 50
31 76
46 54
94 37
...
view save

correct output
1913
40 U
40 U
40 U
40 U
...
view save

user output
(empty)

Error:
code: input/code.cpp:76: int main(): Assertion `orig[i] == fin[i]' failed.

Test 11

Verdict:

input
250
196 74
148 245
203 19
113 198
...
view save

correct output
2370
185 D
185 D
185 D
185 D
...
view save

user output
2370
1 L
1 L
1 L
1 L
...
Truncated

Test 12

Verdict:

input
350
185 170
222 294
183 181
159 171
...
view save

correct output
25660
235 U
235 U
235 U
235 U
...
view save

user output
25660
1 R
1 R
1 R
1 R
...
Truncated

Test 13

Verdict:

input
465
160 163
177 231
220 111
430 330
...
view save

correct output
48963
400 U
400 U
400 U
400 U
...
view save

user output
48963
1 L
1 D
1 D
1 L
...
Truncated

Test 14

Verdict:

input
500
428 393
30 377
76 52
21 218
...
view save

correct output
10301
195 D
195 D
195 D
195 D
...
view save

user output
10301
1 L
1 L
1 L
1 L
...
Truncated

Tasks

A Patuljci-B Npuzzle-C Trojke-D Tenkici-E Bicikli-F Lista-

Submissions (henrikaalto)

2019-07-27 20:41:55 1002019-07-27 20:41:26 02019-07-25 18:37:32 02019-07-25 18:36:59 02019-07-25 18:36:39 02019-07-25 18:34:07 02019-07-25 18:25:03 02019-07-25 18:15:55 02019-07-25 18:15:47 0