oj.uz

Submission #234263

# Submission time Handle Problem Language Result Execution time Memory
234263 2020-05-23T14:59:23 Z VEGAnn Izlet (COI19_izlet) C++14
43 / 100
 754 ms 36728 KB 
#include <bits/stdc++.h>
#define PB push_back
#define a2 array<int,2>
using namespace std;
const int N = 3010;
const int M = 1010;
const int oo = 2e9;
vector<a2> vc;
int ans[N], a[N][N], n, kol = 1, tp;
bool mrk[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> tp;

    assert(n < 3);

    cin >> n;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        cin >> a[i][j];

    if (tp == 2){
        ans[0] = 1;

        for (int i = 1; i < n; i++){
            bool ok = 0;

            fill(mrk, mrk + n, 0);
            int cnt = 0;

            for (int j = i - 1; j >= 0; j--) {
                if (!mrk[ans[j]])
                    cnt++;
                mrk[ans[j]] = 1;

                if (a[i][j] == cnt){
                    ok = 1;
                    ans[i] = ans[j];
                    break;
                }
            }

            if (!ok)
                ans[i] = ++kol;
        }

        for (int i = 0; i < n; i++)
            cout << ans[i] << " ";

        cout << '\n';

        for (int i = 1; i < n; i++)
            cout << i << " " << i + 1 << '\n';
    } else {
        int lst = -1;

        vc.clear();

        for (int i = 0, cur = 1; i < n; i++){
            if (ans[i] > 0) continue;

            ans[i] = cur;

            if (lst >= 0)
                vc.PB({lst, i});

            lst = i;

            for (int j = i + 1; j < n; j++){
                if (ans[j] > 0) continue;

                if (a[i][j] == 1){
                    vc.PB({lst, j});
                    lst = j;
                    ans[j] = cur;
                }
            }

            cur = 3 - cur;
        }

        for (int i = 0; i < n; i++)
            cout << ans[i] << " ";
        cout << '\n';

        for (a2 cr : vc)
            cout << cr[0] + 1 << " " << cr[1] + 1 << '\n';
    }

    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 547 ms 36600 KB Output is correct
3 Correct 549 ms 36600 KB Output is correct
4 Correct 534 ms 36728 KB Output is correct
5 Correct 551 ms 36600 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 35832 KB Output is correct
2 Correct 554 ms 35704 KB Output is correct
3 Correct 736 ms 35844 KB Output is correct
4 Correct 754 ms 35820 KB Output is correct
5 Correct 570 ms 35960 KB Output is correct
6 Correct 599 ms 35836 KB Output is correct
7 Correct 469 ms 30272 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 547 ms 36600 KB Output is correct
3 Correct 549 ms 36600 KB Output is correct
4 Correct 534 ms 36728 KB Output is correct
5 Correct 551 ms 36600 KB Output is correct
6 Correct 535 ms 35832 KB Output is correct
7 Correct 554 ms 35704 KB Output is correct
8 Correct 736 ms 35844 KB Output is correct
9 Correct 754 ms 35820 KB Output is correct
10 Correct 570 ms 35960 KB Output is correct
11 Correct 599 ms 35836 KB Output is correct
12 Correct 469 ms 30272 KB Output is correct
13 Incorrect 545 ms 36640 KB Output isn't correct
14 Halted 0 ms 0 KB -