結果
問題 | No.2731 Two Colors |
ユーザー | nouka28 |
提出日時 | 2024-04-20 09:21:18 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 477 ms / 3,000 ms |
コード長 | 11,008 bytes |
コンパイル時間 | 7,780 ms |
コンパイル使用メモリ | 336,864 KB |
実行使用メモリ | 21,248 KB |
最終ジャッジ日時 | 2024-10-12 04:46:47 |
合計ジャッジ時間 | 15,536 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 469 ms
19,584 KB |
testcase_01 | AC | 477 ms
19,456 KB |
testcase_02 | AC | 463 ms
19,456 KB |
testcase_03 | AC | 5 ms
6,816 KB |
testcase_04 | AC | 24 ms
6,816 KB |
testcase_05 | AC | 15 ms
6,816 KB |
testcase_06 | AC | 67 ms
7,040 KB |
testcase_07 | AC | 72 ms
7,168 KB |
testcase_08 | AC | 11 ms
6,820 KB |
testcase_09 | AC | 275 ms
16,640 KB |
testcase_10 | AC | 5 ms
6,820 KB |
testcase_11 | AC | 288 ms
17,920 KB |
testcase_12 | AC | 274 ms
16,640 KB |
testcase_13 | AC | 245 ms
16,128 KB |
testcase_14 | AC | 124 ms
9,728 KB |
testcase_15 | AC | 11 ms
6,816 KB |
testcase_16 | AC | 119 ms
9,472 KB |
testcase_17 | AC | 162 ms
11,776 KB |
testcase_18 | AC | 29 ms
6,820 KB |
testcase_19 | AC | 118 ms
9,984 KB |
testcase_20 | AC | 176 ms
11,904 KB |
testcase_21 | AC | 31 ms
6,816 KB |
testcase_22 | AC | 291 ms
17,792 KB |
testcase_23 | AC | 68 ms
7,424 KB |
testcase_24 | AC | 34 ms
6,820 KB |
testcase_25 | AC | 3 ms
6,816 KB |
testcase_26 | AC | 227 ms
14,592 KB |
testcase_27 | AC | 290 ms
17,408 KB |
testcase_28 | AC | 188 ms
13,056 KB |
testcase_29 | AC | 59 ms
6,816 KB |
testcase_30 | AC | 103 ms
8,576 KB |
testcase_31 | AC | 68 ms
7,296 KB |
testcase_32 | AC | 362 ms
21,248 KB |
testcase_33 | AC | 1 ms
6,820 KB |
testcase_34 | AC | 1 ms
6,816 KB |
testcase_35 | AC | 2 ms
6,816 KB |
ソースコード
#pragma region template #include<bits/stdc++.h> using namespace std; //other #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; #include<atcoder/all> using namespace atcoder; // #include "atcoder/modint.hpp" using mint = atcoder::modint998244353; using zint = atcoder::modint1000000007; // using mint=modint; #define int long long #define pb push_back #define eb emplace_back #define ep emplace #define len(a) (int)a.size() #define BIT(a,b) ((a)>>(b)&1) // #define endl "\n" // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //using using ll=long long; using i32=signed; using i64=long long; using i128=__int128_t; using ld=long double; using ull=unsigned long long; using uint=unsigned; using pcc=pair<char,char>; using pii=pair<int,int>; using pll=pair<ll,ll>; using pdd=pair<ld,ld>; using vi=vector<int>; using vl=vector<ll>; using vvi=vector<vi>; using vvl=vector<vl>; using vvvi=vector<vvi>; using vvvl=vector<vvl>; template<class T>using V=vector<T>; template<class T>using VV=vector<V<T>>; template<class T>using VVV=vector<VV<T>>; template<class T>using VVVV=vector<VVV<T>>; template<class T>using VVVVV=vector<VVVV<T>>; template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>; template<class T>using pqmax=priority_queue<T>; // template<class T>using pbds=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define chmax(a,b) (a)=max((a),(b)) #define chmin(a,b) (a)=min((a),(b)) const ll LINF=0x1fffffffffffffff; const int INF=0x3fffffff; const int MOD=998244353; const int MOD2=1000000007; const ld PI=3.1415926535897932384626433832795028841971; const ld DINF=numeric_limits<ld>::infinity(); const ld EPS=1e-9; const ll di[]={0,1,0,-1,1,-1,1,-1}; const ll dj[]={1,0,-1,0,1,1,-1,-1}; template<class T> constexpr auto min(T a,T b,T c){ return min(a,min(b,c)); } template<class... T> constexpr auto min(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); } template<class T> constexpr auto max(T a,T b,T c){ return max(a,max(b,c)); } template<class... T> constexpr auto max(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); } #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;i--;) #define rrep2(i,n)for(ll i=n;i--;) #define rrep3(i,a,b)for(ll i=b;i-->(a);) #define rrep4(i,a,b,c)for(ll=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c) #define rrep(...) overload4(__VA_ARGS__,rrpe4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define isum(...) accumulate(all(__VA_ARGS__),0LL) #define dsum(...) accumulate(all(__VA_ARGS__),0.0L) #define Msum(...) accumulate(all(__VA_ARGS__),0_M) #define elif else if #define INT(...) int __VA_ARGS__;input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__) #define STR(...) string __VA_ARGS__;input(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;input(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;input(__VA_ARGS__) //io //in void scan(){} void scan(signed &a){cin>>a;} void scan(unsigned &a){cin>>a;} void scan(long& a){cin>>a;} void scan(long long& a){cin>>a;} void scan(unsigned long long&a){cin>>a;} void scan(char& a){cin>>a;} void scan(float& a){cin>>a;} void scan(double& a){cin>>a;} void scan(long double& a){cin>>a;} void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } } void scan(char a[]){ scanf("%s", a); } void scan(string& a){cin>>a;} template<class T> void scan(vector<T>&); template<class T, int size> void scan(array<T, size>&); template<class T, class L> void scan(pair<T, L>&); template<class T, int size> void scan(T(&)[size]); template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); } template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); } template<class T, int size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); } template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); } template<class T, int size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } template<class T> void scan(T& a){ cin >> a; } void input(){} template<class Head,class...Tail> void input(Head& head,Tail&... tail){scan(head);input(tail...);} //out void puts(){ putchar(' '); } void puts(bool a){ printf("%d", a); } void puts(signed a){ printf("%d", a); } void puts(unsigned a){ printf("%u", a); } void puts(long a){ printf("%ld", a); } void puts(long long a){ printf("%lld", a); } void puts(unsigned long long a){ printf("%llu", a); } void puts(char a){ printf("%c", a); } void puts(char a[]){ printf("%s", a); } // void puts(const char a[]){ printf("%s", a); } void puts(float a){ printf("%.15f", a); } void puts(double a){ printf("%.15f", a); } void puts(long double a){ printf("%.15Lf", a); } void puts(const string& a){ for(auto&& i : a) puts(i); } template<class T> void puts(const complex<T>& a){ if(a.real() >= 0) puts('+'); puts(a.real()); if(a.imag() >= 0) puts('+'); puts(a.imag()); puts('i'); } template<class T> void puts(const vector<T>&); template<class T, int size> void puts(const array<T, size>&); template<class T, class L> void puts(const pair<T, L>& p); template<class T, int size> void puts(const T (&)[size]); template<class T> void puts(const vector<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T> void puts(const deque<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T> void puts(const set<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T> void puts(const multiset<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T, int size> void puts(const array<T, size>& a){ puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T, class L> void puts(const pair<T, L>& p){ putchar('(');puts(p.first); putchar(' '); puts(p.second); putchar(')');} template<class T, int size> void puts(const T (&a)[size]){ puts(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); puts(*i); } } template<class T> void puts(const T& a){ cout << a; } int print(){ putchar('\n'); return 0; } template<class T> int print(const T& t){ puts(t); putchar('\n'); return 0; } template<class Head, class... Tail> int print(const Head& head, const Tail&... tail){ puts(head); putchar(' '); print(tail...); return 0; } #pragma endregion #pragma region commonly used int digitsum(string s){ int res=0; rep(i,(int)s.size()){ res+=s[i]-'0'; } return res; } //乱数系 random_device rnd; mt19937 mt(rnd()); const long long MT_MAX=LINF; uniform_int_distribution<long long> rd(0,MT_MAX); double randd(){ return 1.0*rd(mt)/MT_MAX; } long long randint(long long a,long long b){ // [a,b]の乱数を生成 return a+rd(mt)%(b-a+1); } std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } __int128 parse(string &s) { __int128 ret = 0; for (int i = 0; i < (int)s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } #define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__})) vector<vector<long long>> __MAKE_MAT__(vector<long long> v){ if(v.empty())return vector<vector<long long>>(1,vector<long long>()); long long n=v.back(); v.pop_back(); vector<vector<long long>> ret; vector<vector<long long>> tmp=__MAKE_MAT__(v); for(auto e:tmp)for(long long i=0;i<n;++i){ ret.push_back(e); ret.back().push_back(i); } return ret; } //V',Pを返す。PはVを昇順に並べた時のidx template<class T> pair<vector<T>,vector<int>> sortperm(vector<T> v){ vector<pair<T,int>> sv; for(int i=0;i<(int)v.size();i++){ sv.push_back({v[i],i}); } sort(sv.begin(),sv.end()); vector<T> rv;vector<int> p; for(auto[x,idx]:sv){ rv.push_back(x);p.push_back(idx); } return {rv,p}; } bool isdigit(char x){return '0'<=x&&x<='9';} string ch_to_str(char x){return string{x};} bool isupper(char x){return('A'<=x&&x<='Z');} bool islower(char x){return('a'<=x&&x<='z');} bool ingrid(int x,int y,int h,int w){return 0<=x&&x<h&&0<=y&&y<w;} // #include<boost/multiprecision/cpp_int.hpp> // using lint=boost::multiprecision::cpp_int; #pragma endregion signed main(){ INT(h,w); vvi a(h,vi(w));input(a); set<tuple<int,int,int>> pq1,pq0; set<pair<int,int>> st1,st0; vvi col(h,vi(w,-1)); col[0][0]=1; col[h-1][w-1]=0; pq1.insert({a[0][1],0,1}); pq1.insert({a[1][0],1,0}); pq0.insert({a[h-2][w-1],h-2,w-1}); pq0.insert({a[h-1][w-2],h-1,w-2}); int ans=0; int turn=0; while(1){ ans++; turn^=1; if(turn==1){ auto[v,i,j]=*pq1.begin(); pq1.erase(*pq1.begin()); col[i][j]=turn; rep(k,4){ int ni=i+di[k],nj=j+dj[k]; if(ingrid(ni,nj,h,w)){ if(col[ni][nj]==(1^turn)){ print(ans); exit(0); }else if(col[ni][nj]==-1){ if(!pq1.count({a[ni][nj],ni,nj})){ pq1.insert({a[ni][nj],ni,nj}); } } } } }else{ auto[v,i,j]=*pq0.begin(); pq0.erase(*pq0.begin()); col[i][j]=turn; rep(k,4){ int ni=i+di[k],nj=j+dj[k]; if(ingrid(ni,nj,h,w)){ if(col[ni][nj]==(1^turn)){ print(ans); exit(0); }else if(col[ni][nj]==-1){ if(!pq0.count({a[ni][nj],ni,nj})){ pq0.insert({a[ni][nj],ni,nj}); } } } } } } }