Submission #1053130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053130		Piokemon	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	519 ms	12592 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
bool graf[MAX_N+9][MAX_N+9];
int n;
bool win[MAX_N+2][MAX_N+2][2];
int zost[MAX_N+2][MAX_N+2]; // zawsze ost wymiar to 1, czyli R turn
int skad[MAX_N+2][MAX_N+2]; // zawsze ost wymiar to 0, czyli C turn

int ja=-1;

int start(int N, bool A[MAX_N][MAX_N])
{
    n=N;
    for (int x=0;x<n;x++){
        for (int y=0;y<n;y++)graf[x][y]=A[x][y];
    }
    vector<pair<pair<int,int>,int>> kol;
    for (int x=0;x<n;x++){
        win[x][x][1]=1;
        kol.push_back({{x,x},1});
    }
    for (int x=0;x<n;x++){
        for (int y=0;y<n;y++){
            zost[x][y]=0;
            for (int z=0;z<n;z++){
                if (graf[y][z]==1)zost[x][y]++;
            }
        }
    }
    for (int k=0;k<kol.size();k++){
        int x,y,t;
        x=kol[k].first.first; y=kol[k].first.second; t=kol[k].second;
        if (t==1){
            // R tura
            if (win[x][y][0]==0){
                win[x][y][0]=1;
                skad[x][y]=x;
                kol.push_back({{x,y},0});
            }
            for (int z=0;z<n;z++){
                if (graf[z][x]==1){
                    if (win[z][y][0]==0){
                        win[z][y][0]=1;
                        skad[z][y]=x;
                        kol.push_back({{z,y},0});
                    }
                }
            }
        }
        else{
            // C tura
            for (int z=0;z<n;z++){
                if (graf[z][y]==1){
                    zost[x][z]--;
                    if (zost[x][z]==0){
                        if (win[x][z][1]==0){
                            win[x][z][1]=1;
                            kol.push_back({{x,z},1});
                        }
                    }
                }
            }
        }
    }
    /*cerr << "C turn\n";
    for (int x=0;x<n;x++){
        for (int y=0;y<n;y++) cerr << win[x][y][0] << ' ';
        cerr << '\n';
    }
    cerr << '\n';

    cerr << "R turn\n";
    for (int x=0;x<n;x++){
        for (int y=0;y<n;y++) cerr << win[x][y][1] << ' ';
        cerr << '\n';
    }
    cerr << '\n';

    cerr << "strat\n";
    for (int x=0;x<n;x++){
        for (int y=0;y<n;y++) cerr << skad[x][y] << ' ';
        cerr << '\n';
    }
    cerr << '\n';*/

    for (int x=0;x<n;x++){
        bool ez=1;
        for (int y=0;y<n;y++){
            if (!win[x][y][0])ez=0;
        }
        if (ez){
            ja = x;
            return x;
        }
    }
    return -1;
}

int nextMove(int R)
{
    int nowe=skad[ja][R];
    ja=nowe;
    return nowe;
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int k=0;k<kol.size();k++){
      |                  ~^~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40