Submission #1098048

#TimeUsernameProblemLanguageResultExecution timeMemory
1098048peacebringer1667The Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
1 ms464 KiB
#include<bits/stdc++.h> #define ll long long #define ldb long double #define fi first #define se second #define sza(a) (int)a.size() #define pir pair<int,int> #define pirll pair<ll,ll> using namespace std; const int maxn = 2e3 + 5; struct CTDL{ int x = 0,y = 0,val = 0; bool operator <(const CTDL&other) const{ return (val < other.val); } }; int a[maxn][maxn],Mpos[maxn],mpos[maxn]; vector <CTDL> vec; int input(int n,int m){ for (int i = 1 ; i <= n ; i++){ for (int j = 1 ; j <= m ; j++){ cin >> a[i][j]; vec.push_back({i,j,a[i][j]}); } } sort(vec.begin(),vec.end()); return vec.back().val - vec[0].val; } void refn(int n){ for (int i = 0 ; i <= n ; i++) Mpos[i] = 0; } void refm(int n,int m){ for (int i = 0 ; i <= n ; i++) mpos[i] = m + 1; } bool first_left_right(int n,int m,const vector <int> &vm,const vector <int> &VM){ refn(n); for (int x : vm) Mpos[vec[x].x] = max(Mpos[vec[x].x],vec[x].y); refm(n,m); for (int x : VM) mpos[vec[x].x] = min(mpos[vec[x].x],vec[x].y); int cur = m + 1; for (int i = 1 ; i <= n ; i++){ if (Mpos[i] > cur) return 0; cur = min(cur,mpos[i] - 1); } return 1; } void reim(int n,int m){ for (int i = 0 ; i <= m ; i++) Mpos[i] = 0; } void reimn(int n,int m){ for (int i = 1 ; i <= m ; i++) mpos[i] = n + 1; } bool first_hor(int n,int m,const vector <int> &vm,const vector <int> &VM){ reim(n,m); for (int x : vm) Mpos[vec[x].y] = max(Mpos[vec[x].y],vec[x].x); reimn(n,m); for (int x : VM) mpos[vec[x].y] = min(mpos[vec[x].y],vec[x].x); int cur = n + 1; for (int i = 1 ; i <= m ; i++){ if (Mpos[i] > cur) return 0; cur = min(cur,mpos[i] - 1); } return 1; } bool first_possible(int n,int m,int h){ vector <int> ssm,ssM; for (int i = 0 ; i < vec.size() ; i++) if (vec.back().val - vec[i].val > h) ssm.push_back(i); else break; for (int i = vec.size() - 1 ; i >= 0 ; i--) if (vec[i].val - vec[0].val > h) ssM.push_back(i); else break; if (ssm.size() + ssM.size() > vec.size()) return 0; //ssm left , ssM right return first_left_right(n,m,ssm,ssM) || first_left_right(n,m,ssM,ssm) || first_hor(n,m,ssm,ssM) || first_hor(n,m,ssM,ssm); } bool second_left_right(int n,int m,const vector <int> &vm,const vector <int> VM){ refn(n); for (int x : vm) Mpos[vec[x].x] = max(Mpos[vec[x].x],vec[x].y); refm(n,m); for (int x : VM) mpos[vec[x].x] = min(mpos[vec[x].x],vec[x].y); for (int i = 1 ; i <= n ; i++) if (mpos[i] == m + 1) mpos[i] = mpos[i - 1]; int cur = 0; for (int i = 1 ; i <= n ; i++){ if (mpos[i] < cur) return 0; cur = max(cur,Mpos[i] + 1); } return 1; } bool second_hor(int n,int m,const vector <int> &vm,const vector <int> &VM){ reim(n,m); for (int x : vm) Mpos[vec[x].y] = max(Mpos[vec[x].y],vec[x].x); reimn(n,m); for (int x : VM) mpos[vec[x].y] = min(mpos[vec[x].y],vec[x].x); int cur = 0; for (int i = 1 ; i <= m ; i++){ if (mpos[i] < cur) return 0; cur = max(cur,Mpos[i] + 1); } return 1; } bool second_possible(int n,int m,int h){ vector <int> ssm,ssM; for (int i = 0 ; i < vec.size() ; i++) if (vec.back().val - vec[i].val > h) ssm.push_back(i); for (int i = 0 ; i < vec.size() ; i++) if (vec[i].val - vec[0].val > h) ssM.push_back(i); if (ssm.size() + ssM.size() > vec.size()) return 0; return second_left_right(n,m,ssm,ssM) || second_left_right(n,m,ssM,ssm) || second_hor(n,m,ssm,ssM) || second_hor(n,m,ssM,ssm); } int solve(int n,int m){ int range = input(n,m); int l = 0,r = range,res = 0; while (l <= r){ int w = (l + r)/2; if (first_possible(n,m,w) || second_possible(n,m,w)){ res = w; r = w - 1; } else l = w + 1; } return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,m; cin >> n >> m; cout << solve(n,m); return 0; }

Compilation message (stderr)

joioi.cpp: In function 'bool first_possible(int, int, int)':
joioi.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0 ; i < vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~
joioi.cpp: In function 'bool second_possible(int, int, int)':
joioi.cpp:147:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for (int i = 0 ; i < vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~
joioi.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for (int i = 0 ; i < vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...