oj.uz

Submission #234262

# Submission time Handle Problem Language Result Execution time Memory
234262 2020-05-23T14:56:02 Z VEGAnn Izlet (COI19_izlet) C++14
25 / 100
 679 ms 36088 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++, cur = 3 - cur){
            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;
                }
            }
        }

        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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 35900 KB Output is correct
2 Correct 524 ms 36088 KB Output is correct
3 Correct 612 ms 35832 KB Output is correct
4 Correct 679 ms 35872 KB Output is correct
5 Correct 468 ms 35960 KB Output is correct
6 Correct 512 ms 35832 KB Output is correct
7 Correct 405 ms 30332 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -