Submission #480730

#TimeUsernameProblemLanguageResultExecution timeMemory
480730MonkeyKingThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
707 ms31812 KiB
//Original Code: //#include <numeric> //#include <iostream> //#include <algorithm> //#include <cmath> //#include <stdio.h> //#include <stdlib.h> //#include <vector> //#include <map> //#include <queue> //#include <set> //#include <string> //#include <string.h> //#include <stack> //#include <assert.h> //#include <bitset> //#include <time.h> //#define Endl endl //#define mp make_pair //#define mt make_tuple //#define ll long long //#define ull unsigned long long //#define pii pair<int,int> //#define over(A) {cout<<A<<endl;exit(0);} //#define all(A) A.begin(),A.end() //#define quickcin ios_base::sync_with_stdio(false); //const int mod=1000000007; //const int gmod=3; //const int inf=1039074182; //const double eps=1e-9; //const double pi=3.141592653589793238462643383279; //const ll llinf=2LL*inf*inf; //template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;} //template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;} //inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);} //template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;} //template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;} //template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;} //template <typename T> inline T mabs(T x) {return (x<0?-x:x);} //using namespace std; //int n,m; //int a[2005][2005]; //int b[2005][2005]; //int bel[2005][2005]; //pair<int,pii> mn,mx; //int res; // //inline bool check(int mid) //{ // int x=mn.first,y=mx.first; // int pre=m; // for(int i=0;i<n;i++) // { // for(int j=0;j<pre;j++) // { // if(a[i][j]-x>mid) // { // pre=j; // break; // } // } // for(int j=pre;j<m;j++) // { // if(y-a[i][j]>mid) return false; // } // } // return true; //} // //void solve() //{ // if(mn.first>=mx.first && mn.second>=mx.second) return; // int l=0,r=res-1,mid; // while(l<=r) // { // mid=l+r>>1; // if(check(mid)) // { // res=mid; // r=mid-1; // } // else // { // l=mid+1; // } // } //} // //int main() //{ // // freopen("input.txt","r",stdin); // cin>>n>>m; // mn.first=inf; // mx.first=-inf; // for(int i=0;i<n;i++) // { // for(int j=0;j<m;j++) // { // scanf("%d",a[i]+j); // chmax(mx,mp(a[i][j],mp(i,j))); // chmin(mn,mp(a[i][j],mp(i,j))); // } // } // res=mx.first-mn.first; // for(int _=0;_<4;_++) // { // for(int i=0;i<n;i++) // { // for(int j=0;j<m;j++) // { // b[j][n-1-i]=a[i][j]; // } // } // memcpy(a,b,sizeof(b)); // swap(mx.second.first,mx.second.second); // mx.second.second=n-1-mx.second.second; // swap(mn.second.first,mn.second.second); // mn.second.second=n-1-mn.second.second; // swap(n,m); // solve(); // } // cout<<res<<endl; // return 0; //} //substituted with C++ Inliner #include <numeric> #include <iostream> #include <algorithm> #include <cmath> #include <stdio.h> #include <stdlib.h> #include <vector> #include <map> #include <queue> #include <set> #include <string> #include <string.h> #include <stack> #include <assert.h> #include <bitset> #include <time.h> #define Endl endl #define mp make_pair #define mt make_tuple #define ll long long #define ull unsigned long long #define pii pair<int,int> #define over(A) {cout<<A<<endl;exit(0);} #define all(A) A.begin(),A.end() #define quickcin ios_base::sync_with_stdio(false); const int mod=1000000007; const int gmod=3; const int inf=1039074182; const double eps=1e-9; const double pi=3.141592653589793238462643383279; const ll llinf=2LL*inf*inf; template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;} template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;} inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);} template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;} template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;} template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;} template <typename T> inline T mabs(T x) {return (x<0?-x:x);} using namespace std; int n,m; int a[2005][2005]; int b[2005][2005]; int bel[2005][2005]; pair<int,pii> mn,mx; int res; inline bool check(int mid) { int x=mn.first,y=mx.first; int pre=m; for(int i=0;i<n;i++) { for(int j=0;j<pre;j++) { if(a[i][j]-x>mid) { pre=j; break; } } for(int j=pre;j<m;j++) { if(y-a[i][j]>mid) return false; } } return true; } void solve() { if(mn.first>=mx.first && mn.second>=mx.second) return; int l=0,r=res-1,mid; while(l<=r) { mid=l+r>>1; if(check(mid)) { res=mid; r=mid-1; } else { l=mid+1; } } } int main() { // // freopen("input.txt","r",stdin); cin>>n>>m; mn.first=inf; mx.first=-inf; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",a[i]+j); chmax(mx,mp(a[i][j],mp(i,j))); chmin(mn,mp(a[i][j],mp(i,j))); } } res=mx.first-mn.first; for(int _=0;_<4;_++) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { b[j][n-1-i]=a[i][j]; } } memcpy(a,b,sizeof(b)); swap(mx.second.first,mx.second.second); mx.second.second=n-1-mx.second.second; swap(mn.second.first,mn.second.second); mn.second.second=n-1-mn.second.second; swap(n,m); solve(); } cout<<res<<endl; return 0; }

Compilation message (stderr)

joioi.cpp: In function 'void solve()':
joioi.cpp:201:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  201 |   mid=l+r>>1;
      |       ~^~
joioi.cpp: In function 'int main()':
joioi.cpp:224:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |    scanf("%d",a[i]+j);
      |    ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...