Submission #841189

#	Time	Username	Problem	Language	Result	Execution time	Memory
841189		daoda	Mecho (IOI09_mecho)	C++17	100 / 100	299 ms	3280 KiB

mecho

#include <bits/stdc++.h>

using namespace std;
#define FOR(a, b) for(ll i = a; i < b; i++)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

typedef long long int ll;
typedef pair<ll, ll> pll; // comments that are mixed
typedef vector<ll> vll; // in with code are placed
typedef vector<pll> vpll; // on the right side
typedef vector<bool> vb;

struct Object {
    ll row,col;
    char type='H';
};

ll n,s;
vector<vector<char>> grid, stat; 
vll dr={0,0,-1,1}, dc={-1, 1, 0, 0};
vector<Object> hives;
Object bear, home;

void bfs(queue<Object>&bfs_list,function<bool(char&,char&)> cond,char rep,ll iters = 1){
    FOR(0, iters) {
        
        ll sz=bfs_list.size();
        
        FOR(0, sz) {
            
            Object cur=bfs_list.front();
            bfs_list.pop();
            
            FOR(0, 4) {
                
                char& cell = stat[cur.row + dr[i]][cur.col + dc[i]];
                if(cond(stat[cur.row][cur.col], cell)) {
                    cell=rep;
                    bfs_list.push((Object){.row=cur.row+dr[i],.col=cur.col+dc[i]});
                }
            }
        }
    }
}

bool cond1(char& a,char& b) { return (b == 'G' || b == 'M'); }
bool cond2(char& a,char& b) { return (a == 'M' && (b == 'G' || b== 'D')); }

bool f(ll max_t) {
    stat=grid;
    
    queue<Object> bfs_list1, bfs_list2;
    
    FOR(0, hives.size()) bfs_list1.push(hives[i]);
    bfs_list2.push(bear);
    
    
    
    bfs(bfs_list1,cond1,'H',max_t);
    
    while(bfs_list2.size()) {
       bfs(bfs_list2,cond2,'M', s);
       if(stat[home.row][home.col] == 'M') return true;
       bfs(bfs_list1,cond1,'H', 1);
    }
    
    return false;
}

int main() {
    fast

    cin >> n >> s;
    grid.resize(n+2, vector<char>(n+2, 'T'));
    
    
    FOR(1, n+1) {
        for(ll i2=1; i2 < n+1; i2++) {
            cin >> grid[i][i2];
            if(grid[i][i2] == 'H') hives.push_back((Object){.row=i,.col=i2});
            if(grid[i][i2] == 'M') bear = (Object){.row=i,.col=i2,.type='M'};
            if(grid[i][i2] == 'D') home = (Object){.row=i,.col=i2,.type='D'};
        }
    }

    ll lb=-1, upb=n*n;
    while(lb < upb) {
        ll mid=(lb + upb + 1) /2 ;
        if(f(mid)) lb=mid;
        else upb = mid - 1 ;
    }
    cout << lb;

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool f(ll)':
mecho.cpp:4:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Object>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(a, b) for(ll i = a; i < b; i++)
      |                                 ~~^~~~~~~~~
    5 | #define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    6 | 
      |                                    
    7 | typedef long long int ll;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~          
    8 | typedef pair<ll, ll> pll; // comments that are mixed
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    9 | typedef vector<ll> vll; // in with code are placed
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   10 | typedef vector<pll> vpll; // on the right side
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   11 | typedef vector<bool> vb;
      | ~~~~~~~~~~~~~~~~~~~~~~~~           
   12 | 
      |                                    
   13 | struct Object {
      | ~~~~~~~~~~~~~~~                    
   14 |     ll row,col;
      |     ~~~~~~~~~~~                    
   15 |     char type='H';
      |     ~~~~~~~~~~~~~~                 
   16 | };
      | ~~                                 
   17 | 
      |                                    
   18 | ll n,s;
      | ~~~~~~~                            
   19 | vector<vector<char>> grid, stat;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   
   20 | vll dr={0,0,-1,1}, dc={-1, 1, 0, 0};
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   21 | vector<Object> hives;
      | ~~~~~~~~~~~~~~~~~~~~~              
   22 | Object bear, home;
      | ~~~~~~~~~~~~~~~~~~                 
   23 | 
      |                                    
   24 | void bfs(queue<Object>&bfs_list,function<bool(char&,char&)> cond,char rep,ll iters = 1){
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   25 |     FOR(0, iters) {
      |     ~~~~~~~~~~~~~~~                
   26 | 
      |                                    
   27 |         ll sz=bfs_list.size();
      |         ~~~~~~~~~~~~~~~~~~~~~~     
   28 | 
      |                                    
   29 |         FOR(0, sz) {
      |         ~~~~~~~~~~~~               
   30 | 
      |                                    
   31 |             Object cur=bfs_list.front();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   32 |             bfs_list.pop();
      |             ~~~~~~~~~~~~~~~        
   33 | 
      |                                    
   34 |             FOR(0, 4) {
      |             ~~~~~~~~~~~            
   35 | 
      |                                    
   36 |                 char& cell = stat[cur.row + dr[i]][cur.col + dc[i]];
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 |                 if(cond(stat[cur.row][cur.col], cell)) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   38 |                     cell=rep;
      |                     ~~~~~~~~~      
   39 |                     bfs_list.push((Object){.row=cur.row+dr[i],.col=cur.col+dc[i]});
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |                 }
      |                 ~                  
   41 |             }
      |             ~                      
   42 |         }
      |         ~                          
   43 |     }
      |     ~                              
   44 | }
      | ~                                  
   45 | 
      |                                    
   46 | bool cond1(char& a,char& b) { return (b == 'G' || b == 'M'); }
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   47 | bool cond2(char& a,char& b) { return (a == 'M' && (b == 'G' || b== 'D')); }
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   48 | 
      |                                    
   49 | bool f(ll max_t) {
      | ~~~~~~~~~~~~~~~~~~                 
   50 |     stat=grid;
      |     ~~~~~~~~~~                     
   51 | 
      |                                    
   52 |     queue<Object> bfs_list1, bfs_list2;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   53 | 
      |                                    
   54 |     FOR(0, hives.size()) bfs_list1.push(hives[i]);
      |     ~~~~~~~~~~~~~~~~~~~            
mecho.cpp:54:5: note: in expansion of macro 'FOR'
   54 |     FOR(0, hives.size()) bfs_list1.push(hives[i]);
      |     ^~~

• Subtask 1: 100 / 100