Submission #977177

#	Time	Username	Problem	Language	Result	Execution time	Memory
977177		LucaIlie	Vision Program (IOI19_vision)	C++17	32 / 100	6 ms	1492 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200;
int isOnLineId[MAX_N], isOnColumnId[MAX_N];
int isDifLineId[MAX_N], isDifColumnId[MAX_N];

int n, m, k;

int cellId( int l, int c ) {
    if ( l < 0 || c < 0 || l >= n || c >= m )
        return -1;
    return l * m + c;
}

void construct_network( int N, int M, int K ) {
    n = N, m = M, k = K;

    vector<int> skipL( n, 0 ), skipC( m, 0 );

    for ( int i = 0; i < 3 * (n / 95); i++ )
        skipL[i] = 1;
    for ( int i = 0; i < 3 * (m / 95); i++ )
        skipC[i] = 1;
    random_shuffle( skipL.begin(), skipL.begin() + n / 2 );
    random_shuffle( skipC.begin(), skipC.begin() + m / 2 );

    int id = n * m;
    for ( int l = 0; l < n; l++ ) {
        vector<int> ids;
        for ( int c = 0; c < m; c++ )
            ids.push_back( cellId( l, c ) );
        add_or( ids );
        isOnLineId[l] = id;
        id++;
    }
    for ( int c = 0; c < m; c++ ) {
        vector<int> ids;
        for ( int l = 0; l < n; l++ )
            ids.push_back( cellId( l, c ) );
        add_or( ids );
        isOnColumnId[c] = id;
        id++;
    }

    vector<int> idsDifL;
    for ( int difL = 1; difL < n; difL++ ) {
        vector<int> ids;
        for ( int l = 0; l + difL < n; l++ ) {
            add_and( { isOnLineId[l], isOnLineId[l + difL] } );
            ids.push_back( id );
            id++;
            if ( skipL[difL] )
                break;
        }
        add_or( ids );
        isDifLineId[difL] = id;
        idsDifL.push_back( id );
        id++;
    }
    if ( n > 1 ) {
        add_or( idsDifL );
        add_not( id );
        id++;
        isDifLineId[0] = id;
        id++;
    }

    vector<int> idsDifC;
    for ( int difC = 1; difC < m; difC++ ) {
        vector<int> ids;
        for ( int c = 0; c + difC < m; c++ ) {
            add_and( { isOnColumnId[c], isOnColumnId[c + difC] } );
            ids.push_back( id );
            id++;
            if ( skipC[difC] )
                break;
        }
        add_or( ids );
        isDifColumnId[difC] = id;
        idsDifC.push_back( id );
        id++;
    }
    if ( m > 1 ) {
        add_or( idsDifC );
        add_not( id );
        id++;
        isDifColumnId[0] = id;
        id++;
    }

    vector<int> ids;
    for ( int i = 0; i <= k; i++ ) {
        if ( n == 1 && i == 0 ) {
            ids.push_back( isDifColumnId[k - i] );
            continue;
        }
        if ( m == 1 && k - i == 0 ) {
            ids.push_back( isDifLineId[i] );
            continue;
        }
        if ( isDifLineId[i] == 0 || isDifColumnId[k - i] == 0 )
            continue;

        add_and( { isDifLineId[i], isDifColumnId[k - i] } );
        ids.push_back( id );
        id++;
    }

    add_or( ids );
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 0 / 12
• Subtask 6: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19