Submission #111290

# Submission time Handle Problem Language Result Execution time Memory
111290 2019-05-14T15:40:25 Z tatyam Robots (APIO13_robots) C++17
60 / 100
1500 ms 122660 KB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ull=unsigned long long;
using uint=unsigned int;
using pcc=pair<char,char>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<double,double>;
using tuplis=pair<ll,pll>;
using tuplis2=pair<pll,ll>;
template<class T> using pq=priority_queue<T,vector<T>,greater<T>>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const vector<ll>four{0,1,0,-1,0};
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _rep1(n) for(ll i=0;i<n;++i)
#define _rep2(i,n) for(ll i=0;i<n;++i)
#define _rep3(i,a,b) for(ll i=a;i<b;++i)
#define _rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) for(ll i=n-1;i>=0;i--)
#define _rrep2(i,n) for(ll i=n-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)
#define each(i,a) for(auto &i:a)
#define sum(...) accumulate(range(__VA_ARGS__),0LL)
#define dsum(...) accumulate(range(__VA_ARGS__),double(0))
#define _range(i) (i).begin(),(i).end()
#define _range2(i,k) (i).begin(),(i).begin()+k
#define _range3(i,a,b) (i).begin()+a,(i).begin()+b
#define range(...) _overload3(__VA_ARGS__,_range3,_range2,_range)(__VA_ARGS__)
#define _rrange(i) (i).rbegin(),(i).rend()
#define _rrange2(i,k) (i).rbegin(),(i).rbegin()+k
#define _rrange3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rrange(...) _overload3(__VA_ARGS__,_rrange3,_rrange2,_rrange)(__VA_ARGS__)
#define elif else if
#define unless(a) if(!(a))
#define mp make_pair
#define mt make_tuple
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
template<class T> inline constexpr T min(vector<T> &v){return *min_element(range(v));}
inline char min(string &v){return *min_element(range(v));}
template<class T> inline constexpr T max(vector<T> &v){return *max_element(range(v));}
inline char max(string &v){return *max_element(range(v));}
inline constexpr ll intpow(ll a,ll b){ll ans=1;for(ll i=1;b;i*=2){if(b&i){b^=i;ans*=a;}a*=a;}return ans;}
inline constexpr ll modpow(ll a,ll b,ll mod = MOD){ll ans=1;for(ll i=1;b;i*=2){if(b&i){b^=i;ans*=a;ans%=mod;}a*=a;a%=mod;}return ans;}
template<typename T>
inline constexpr bool update_min(T &mn,const T &cnt){if(mn>cnt){mn=cnt;return 1;}else return 0;}
template<typename T>
inline constexpr bool update_max(T &mx,const T &cnt){if(mx<cnt){mx=cnt;return 1;}else return 0;}
inline int scan(){ return getchar(); }
inline void scan(int &a){ scanf("%d", &a); }
inline void scan(unsigned &a){ scanf("%u", &a); }
inline void scan(long &a){ scanf("%ld", &a); }
inline void scan(long long &a){ scanf("%lld", &a); }
inline void scan(unsigned long long &a){ scanf("%llu", &a); }
inline void scan(char &a){ cin >> a; }
inline void scan(float &a){ scanf("%f", &a); }
inline void scan(double &a){ scanf("%lf", &a); }
inline void scan(long double &a){ scanf("%Lf", &a); }
inline void scan(vector<bool> &vec){ for(unsigned i = 0; i < vec.size(); i++) { int a; scan(a); vec[i] = a; } }
inline void scan(string &a){ cin >> a; }
template<class T> inline void scan(vector<T> &vec);
template<class T, size_t size> inline void scan(array<T, size> &vec);
template<class T, class L> inline void scan(pair<T, L> &p);
template<class T, size_t size> inline void scan(T (&vec)[size]);
template<class T> inline void scan(vector<T> &vec){ for(auto &i : vec) scan(i); }
template<class T, size_t size> inline void scan(array<T, size> &vec){ for(auto &i : vec) scan(i); }
template<class T, class L> inline void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template<class T, size_t size> inline void scan(T (&vec)[size]){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(T &a){ cin>>a; }
inline void in(){}
template <class Head, class... Tail> inline void in(Head &head, Tail&... tail){ scan(head); in(tail...); }
inline void print(){ putchar('\n'); }
inline void print(const bool &a){ printf("%d", a); }
inline void print(const int &a){ printf("%d", a); }
inline void print(const unsigned &a){ printf("%u", a); }
inline void print(const long &a){ printf("%ld", a); }
inline void print(const long long &a){ printf("%lld", a); }
inline void print(const unsigned long long &a){ printf("%llu", a); }
inline void print(const char &a){ printf("%c", a); }
inline void print(const char a[]){ printf("%s", a); }
inline void print(const float &a){ printf("%.10f", a); }
inline void print(const double &a){ printf("%.10f", a); }
inline void print(const long double &a){ printf("%.10Lf", a); }
template<class T> void print(const vector<T> &vec);
template<class T, size_t size> void print(const array<T, size> &vec);
template<class T, class L> void print(const pair<T, L> &p);
template<class T, size_t size> inline void print(const T (&vec)[size]);
template<class T> void print(const vector<T> &vec){ print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size> &vec){ print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L> &p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> inline void print(const T (&vec)[size]){ print(vec[0]); for(auto i = vec; ++i != end(vec); ){ putchar(' '); print(*i); } }
template<class T> inline void print(const T &a){ cout << a; }
inline int out(){ putchar('\n'); return 0; }
template<class T> inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> inline int out(const Head &head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
template <class T> inline void err(T t){cerr<<t<<'\n';}
inline void err(){cerr<<'\n';}
inline int yes(const bool &i){return out(i?"yes":"no");}
inline int Yes(const bool &i){return out(i?"Yes":"No");}
inline int YES(const bool &i){return out(i?"YES":"NO");}
inline int Yay(const bool &i){return out(i?"Yay!":":(");}
inline int Possible(const bool &i){return out(i?"Possible":"Impossible");}
inline int POSSIBLE(const bool &i){return out(i?"POSSIBLE":"IMPOSSIBLE");}
inline void Case(ll i){printf("Case #%lld: ",i);}

#define ll int
#define pll pii
#define LINF INF
#define tuplis pair<int,pii>
ll h,w,n;
vec(string,s,500);
vvv(pll,nxt,500,500,4,{LINF,LINF});
bool valid(ll x,ll y,ll d){
    if(x<0||y<0||x>=h||y>=w)return 0;
    if(s[x][y]=='x')return 0;
    return 1;
}
pll make_next(ll x,ll y,ll d){
    if(nxt[x][y][d].first!=LINF)return nxt[x][y][d];
    nxt[x][y][d]={-1,-1};
    ll d2=d;
    if(s[x][y]=='A')d2--;
    if(s[x][y]=='C')d2++;
    d2&=3;
    if(valid(x+four[d2],y+four[d2+1],d2))return nxt[x][y][d]=make_next(x+four[d2],y+four[d2+1],d2);
    return nxt[x][y][d]={x,y};
}
int main(){
    in(n,w,h);
    rep(h)in(s[i]);
    rep(h)rep(j,w)rep(k,4)make_next(i,j,k);
    ll cost[n+1][n+1][h][w];
    fill(cost[0][0][0],cost[n+1][0][0],INF);
    rep(i,n){
        vv(bool,used,h,w);
        auto&at=cost[i][i+1];
        queue<pll>q;
        rep(j,h)rep(k,w)if(s[j][k]=='1'+i){
            at[j][k]=0;
            q.push({j,k});
        }
        while(q.size()){
            ll x,y;
            tie(x,y)=q.front();
            q.pop();
            if(used[x][y])continue;
            used[x][y]=1;
            rep(4){
                ll x2,y2;
                tie(x2,y2)=nxt[x][y][i];
                if(update_min(at[x2][y2],at[x][y]+1))q.push({x2,y2});
            }
        }
    }
    rep(i,2,n+1)rep(j,i,n+1){
        auto&at=cost[j-i][j];
        rep(k,1,i)rep(x,h)rep(y,w)update_min(at[x][y],cost[j-i][j-k][x][y]+cost[j-k][j][x][y]);
        queue<pll>q;
        pq<tuplis>q2;
        rep(x,h)rep(y,w)q2.push({at[x][y],{x,y}});
        vv(bool,used,h,w);
        while(q.size()||q2.size()){
            ll x,y;
            if(q2.empty()){
                tie(x,y)=q.front();
                q.pop();
            }
            elif(q.empty()){
                tie(x,y)=q2.top().second;
                q2.pop();
            }
            elif(at[q.front().first][q.front().second]<q2.top().first){
                tie(x,y)=q.front();
                q.pop();
            }
            else{
                tie(x,y)=q2.top().second;
                q2.pop();
            }
            if(used[x][y])continue;
            used[x][y]=1;
            rep(4){
                ll x2,y2;
                tie(x2,y2)=nxt[x][y][i];
                if(update_min(at[x2][y2],at[x][y]+1))q.push({x2,y2});
            }
        }
    }
    ll ans=LINF;
    each(i,cost[0][n])update_min(ans,*min_element(i,i+w));
    if(ans==LINF)return out(-1);
    out(ans);
}

Compilation message

robots.cpp: In function 'void scan(int&)':
robots.cpp:72:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 inline void scan(int &a){ scanf("%d", &a); }
                           ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 27 ms 18040 KB Output is correct
2 Correct 23 ms 17920 KB Output is correct
3 Correct 24 ms 17920 KB Output is correct
4 Correct 23 ms 18048 KB Output is correct
5 Correct 24 ms 18048 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 27 ms 18040 KB Output is correct
2 Correct 23 ms 17920 KB Output is correct
3 Correct 24 ms 17920 KB Output is correct
4 Correct 23 ms 18048 KB Output is correct
5 Correct 24 ms 18048 KB Output is correct
6 Correct 28 ms 17980 KB Output is correct
7 Correct 25 ms 18048 KB Output is correct
8 Correct 24 ms 18048 KB Output is correct
9 Correct 26 ms 18048 KB Output is correct
10 Correct 24 ms 18008 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 27 ms 18040 KB Output is correct
2 Correct 23 ms 17920 KB Output is correct
3 Correct 24 ms 17920 KB Output is correct
4 Correct 23 ms 18048 KB Output is correct
5 Correct 24 ms 18048 KB Output is correct
6 Correct 28 ms 17980 KB Output is correct
7 Correct 25 ms 18048 KB Output is correct
8 Correct 24 ms 18048 KB Output is correct
9 Correct 26 ms 18048 KB Output is correct
10 Correct 24 ms 18008 KB Output is correct
11 Correct 652 ms 55476 KB Output is correct
12 Correct 41 ms 19576 KB Output is correct
13 Correct 468 ms 43364 KB Output is correct
14 Correct 924 ms 55344 KB Output is correct
15 Correct 680 ms 55376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 27 ms 18040 KB Output is correct
2 Correct 23 ms 17920 KB Output is correct
3 Correct 24 ms 17920 KB Output is correct
4 Correct 23 ms 18048 KB Output is correct
5 Correct 24 ms 18048 KB Output is correct
6 Correct 28 ms 17980 KB Output is correct
7 Correct 25 ms 18048 KB Output is correct
8 Correct 24 ms 18048 KB Output is correct
9 Correct 26 ms 18048 KB Output is correct
10 Correct 24 ms 18008 KB Output is correct
11 Correct 652 ms 55476 KB Output is correct
12 Correct 41 ms 19576 KB Output is correct
13 Correct 468 ms 43364 KB Output is correct
14 Correct 924 ms 55344 KB Output is correct
15 Correct 680 ms 55376 KB Output is correct
16 Execution timed out 1524 ms 122660 KB Time limit exceeded
17 Halted 0 ms 0 KB -