제출 #233373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233373		VEGAnn	Izlet (COI19_izlet)	C++14	0 / 100	594 ms	37000 KiB

izlet

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 3010;
const int M = 310;
const int md = int(1e9) + 7;
const int TIM = 20000;
bitset<N> bad[N], bs;
int n, mat[N][N], pre[N], kol = 0, col[N];

int get(int x) { return (pre[x] == x ? x : pre[x] = get(pre[x])); }

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

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

    cin >> n;

    assert(n == 2);

    cin >> n;

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

    for (int i = 0; i < n; i++) {
        pre[i] = i;
        col[i] = -1;

        for (int j = 0; j < n; j++)
            bs[j] = 0;

        bs[i] = 1;

        for (int j = i + 1, kol = 1; j < n; j++)
            if (mat[i][j] > kol){
                kol++;
                bad[j] |= bs;
                bs[j] = 1;
            }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++)
            bs[j] = 0;

        bs[i] = 1;

        for (int j = i - 1, kol = 1; j >= 0; j--)
            if (mat[i][j] > kol){
                kol++;
                bad[j] |= bs;
                bs[j] = 1;
            }
    }

//    for (int i = 0; i < n; i++){
//        for (int j = 0; j < n; j++)
//            cout << bad[i][j];
//        cout << '\n';
//    }

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (!bad[i][j] && !bad[j][i])
                pre[get(i)] = get(j);

    for (int i = 0; i < n; i++){
        int x = get(i);

        if (col[x] < 0)
            col[x] = kol++;

        cout << col[x] + 1 << " ";
    }

    cout << '\n';

    for (int i = 0; i < n; i++)
        cout << i + 1 << " " << i + 2 << '\n';

    return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57