제출 #234263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234263		VEGAnn	Izlet (COI19_izlet)	C++14	43 / 100	754 ms	36728 KiB

izlet

#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 / 18
• Subtask 2: 25 / 25
• Subtask 3: 0 / 57