oj.uz

Submission #671267

# Submission time Handle Problem Language Result Execution time Memory
671267 2022-12-12T15:18:42 Z mdn2002 Cop and Robber (BOI14_coprobber) C++14
0 / 100
 1 ms 336 KB 
#include<bits/stdc++.h>
using namespace std;
int n , iswin [502][502][3] , nxt [502][502][3] , cnt [502][502] , cur;
bool a [500][500];
int start(int N, bool A [500][500])
{
    n = N;
    vector < pair < pair < int , int > , int > > v;
    for ( int i = 0 ; i < n ; i ++ )
    {
        int cntt = 0;
        for ( int j = 0 ; j < n ; j ++ )
        {
            cntt += A [i][j];
            a [i][j] = A [i][j];
        }
        for ( int j = 0 ; j < n ; j ++ ) cnt [j][i] = cntt;
        iswin [i][i][0] = 1;
        iswin [i][i][1] = 1;
        v . push_back ( { { i , i } , 0 } );
        v . push_back ( { { i , i } , 1 } );
    }

    while ( v . size () )
    {
        int did = 0;
        pair < pair < int , int > , int > p = * -- v . end ();
        v . pop_back ();
        int i = p . first . first , j = p . first . second , z = p . second;
        for ( int k = 0 ; k < n ; k ++ )
        {
            int nx = i , ny = j , can = 0 , zz = z ^ 1;
            if ( zz == 0 )
            {
                ny = k;
                if ( a [j][k] ) can = 1;
            }
            else
            {
                nx = k;
                if ( a [i][k] ) can = 1;
            }
            if ( zz == 1 && i == k ) can = 1;
            if ( can == 0 || iswin [nx][ny][zz] ) continue;
            if ( zz == 0 )
            {
                iswin [nx][ny][zz] = 1;
                v . push_back ( { { nx , ny } , zz } );
            }
            else
            {
                cnt [nx][ny] --;
                if ( cnt [nx][ny] == 0 )
                {
                    iswin [nx][ny][zz] = 1;
                    v . push_back ( { { nx , ny } , zz } );
                }
            }
        }
    }
    for ( int i = 0 ; i < n ; i ++ )
    {
        int num = 0;
        for ( int j = 0 ; j < n ; j ++ )
        {
            if ( iswin [i][j][0] ) num ++;
        }
        if ( num == n )
        {
            cur = i;
            return i;
        }
    }
    return -1;
}


int nextMove(int R) {
    if ( cur == -1 ) return -1;
    cur = nxt [cur][R][0];
    return cur;
}

/*
int main()
{
    cin >> n;
    for ( int i = 0 ; i < n ; i ++ )
    {
        for ( int j = 0 ; j < n ; j ++ ) cin >> a [i][j];
    }

    cout << start ( n , a ) << endl;
    for ( int i = 0 ; i < n ; i ++ )
    {
        for ( int j = 0 ; j < n ; j ++ )
        {
            if ( iswin [i][j] ) cout << ' ' << i << ' ' << j << endl;
        }
    }
    while ( true )
    {
        int x;
        cin >> x;
        cout << ' ' << nextMove ( x ) << endl;
    }
}


*/

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:26:13: warning: unused variable 'did' [-Wunused-variable]
   26 |         int did = 0;
      |             ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 292 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -