Submission #790625

#TimeUsernameProblemLanguageResultExecution timeMemory
790625nnhzzzRobots (APIO13_robots)C++14
100 / 100
432 ms105904 KiB
// 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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...