oj.uz

답안 #790625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790625 2023-07-23T02:16:45 Z nnhzzz 로봇 (APIO13_robots) C++14
100 / 100
 432 ms 105904 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <cassert>
#include <random>

using namespace std;

#define    SORT_UNIQUE(v)  sort(ALL(v)),(v).resize(unique(ALL(v))-(v).begin())
#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define           RALL(x)  (x).rbegin(),(x).rend()
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define               INF  0x3f3f3f3f
#define                ll  long long
#define               ull  unsigned long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define      RESET(x,val)  memset((x),(val),sizeof(x))
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
//-------------------------------------------------------------//
const int oo = 0x3f3f3f3f,LOG = 20,MAXN = 5e2+3,N = 1e2+3;
const int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int tran(int a, int b){ return (a<<10)|b; }
int _fi(int a){ return a>>10; }
int _se(int a){ return a&1023; }

int to[MAXN][MAXN][4],instk[MAXN][MAXN],pos[10],dp[10][10][MAXN][MAXN];
char s[MAXN][MAXN];
stack<int> stk; queue<int> q; vpii ins;
int n,w,h,maxtran = tran(oo,oo),invalid = tran(-1,-1);

int f(int x, int y, int t){
    int &res = to[x][y][t];
    if(res!=maxtran){
        return res;
    }
    if(s[x][y]=='x'){
        return res = invalid;
    }
    stk.push(tran(x,y));
    instk[x][y] = 1;
    int nx = x+dir[t][0],ny = y+dir[t][1];
    if(nx>=0 && ny>=0 && nx<h && ny<w){
        if(instk[nx][ny]){
            res = invalid;
        }else{
            if(s[nx][ny]=='x'){
                res = tran(x,y);
            }else{
                if(s[nx][ny]=='A'){
                    res = f(nx,ny,(t+3)%4);
                }else{
                    if(s[nx][ny]=='C'){
                        res = f(nx,ny,(t+1)%4);
                    }else{
                        res = f(nx,ny,t);
                    }
                }
            }
        }
    }else{
        res = tran(x,y);
    }
    stk.pop();
    instk[x][y] = 0;
    return res;
}

void bfs(int d[MAXN][MAXN], int type, int a, int b, int c){
    if(type==0){
        ins.emplace_back(0,pos[a]);
    }else{
        REP(i,0,h-1){
            REP(j,0,w-1){
                int val = dp[a][b][i][j]+dp[b+1][c][i][j];
                if(val<d[i][j]){
                    ins.emplace_back(val,tran(i,j));
                }
            }
        }
    }
    sort(ALL(ins),greater<pii>());
    while(SZ(ins)!=0){
        auto [wit,it] = ins.back();
        if(mini(d[_fi(it)][_se(it)],wit)){
            q.push(it);
        }
        ins.pop_back();
        while(SZ(q)!=0){
            int c = q.front(); q.pop();
            int cdis = d[_fi(c)][_se(c)];
            while(SZ(ins)!=0 && cdis+1>ins.back().fi){
                wit = ins.back().fi; it = ins.back().se;
                if(mini(d[_fi(it)][_se(it)],wit)){
                    q.push(it);
                }
                ins.pop_back();
            }
            for(auto i:to[_fi(c)][_se(c)]){
                if(i==invalid){
                    continue;
                }
                if(mini(d[_fi(i)][_se(i)],cdis+1)){
                    q.push(i);
                }
            }
        }
    }
}

void solve(){
    cin >> n >> w >> h;
    REP(i,0,h-1){
        REP(j,0,w-1){
            cin >> s[i][j];
            if(s[i][j]>='1' && s[i][j]<='9'){
                pos[s[i][j]-'0'] = tran(i,j);
            }
            REP(k,0,3){
                to[i][j][k] = tran(oo,oo);
            }
        }
    }
    REP(i,0,h-1){
        REP(j,0,w-1){
            REP(k,0,3){
                f(i,j,k);
            }
        }
    }
    memset(dp,0x3f3f3f3f,sizeof dp);
    REP(len,1,n){
        REP(l,1,n-len+1){
            int r = l+len-1;
            if(l==r){
                bfs(dp[l][r],0,l,-1,-1);
            }else{
                REP(mid,l,r-1){
                    bfs(dp[l][r],1,l,mid,r);
                }
            }
        }
    }
    int res = oo;
    REP(i,0,h-1){
        REP(j,0,w-1){
            mini(res,dp[1][n][i][j]);
        }
    }
    cout << (res==oo?-1:res);
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

robots.cpp: In function 'void bfs(int (*)[503], int, int, int, int)':
robots.cpp:145:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  145 |         auto [wit,it] = ins.back();
      |              ^
robots.cpp: In function 'int main()':
robots.cpp:219:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:224:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:225:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 99232 KB Output is correct
2 Correct 40 ms 99340 KB Output is correct
3 Correct 37 ms 99276 KB Output is correct
4 Correct 38 ms 99292 KB Output is correct
5 Correct 38 ms 99396 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 99232 KB Output is correct
2 Correct 40 ms 99340 KB Output is correct
3 Correct 37 ms 99276 KB Output is correct
4 Correct 38 ms 99292 KB Output is correct
5 Correct 38 ms 99396 KB Output is correct
6 Correct 37 ms 99236 KB Output is correct
7 Correct 33 ms 99256 KB Output is correct
8 Correct 37 ms 99284 KB Output is correct
9 Correct 41 ms 99272 KB Output is correct
10 Correct 37 ms 99352 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 99232 KB Output is correct
2 Correct 40 ms 99340 KB Output is correct
3 Correct 37 ms 99276 KB Output is correct
4 Correct 38 ms 99292 KB Output is correct
5 Correct 38 ms 99396 KB Output is correct
6 Correct 37 ms 99236 KB Output is correct
7 Correct 33 ms 99256 KB Output is correct
8 Correct 37 ms 99284 KB Output is correct
9 Correct 41 ms 99272 KB Output is correct
10 Correct 37 ms 99352 KB Output is correct
11 Correct 89 ms 102852 KB Output is correct
12 Correct 42 ms 102508 KB Output is correct
13 Correct 51 ms 102580 KB Output is correct
14 Correct 171 ms 103048 KB Output is correct
15 Correct 81 ms 102748 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 99232 KB Output is correct
2 Correct 40 ms 99340 KB Output is correct
3 Correct 37 ms 99276 KB Output is correct
4 Correct 38 ms 99292 KB Output is correct
5 Correct 38 ms 99396 KB Output is correct
6 Correct 37 ms 99236 KB Output is correct
7 Correct 33 ms 99256 KB Output is correct
8 Correct 37 ms 99284 KB Output is correct
9 Correct 41 ms 99272 KB Output is correct
10 Correct 37 ms 99352 KB Output is correct
11 Correct 89 ms 102852 KB Output is correct
12 Correct 42 ms 102508 KB Output is correct
13 Correct 51 ms 102580 KB Output is correct
14 Correct 171 ms 103048 KB Output is correct
15 Correct 81 ms 102748 KB Output is correct
16 Correct 70 ms 104820 KB Output is correct
17 Correct 432 ms 105904 KB Output is correct
18 Correct 90 ms 105348 KB Output is correct
19 Correct 68 ms 104808 KB Output is correct
20 Correct 285 ms 105904 KB Output is correct