oj.uz

Submission #233375

# Submission time Handle Problem Language Result Execution time Memory
233375 2020-05-20T10:47:32 Z VEGAnn Izlet (COI19_izlet) C++14
0 / 100
 622 ms 36984 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -