Submission #938879

#TimeUsernameProblemLanguageResultExecution timeMemory
938879AndreyThe Kingdom of JOIOI (JOI17_joioi)C++14
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> using namespace std; int haha[2001][2001]; int n,m; bool check(int a) { int x = -1; vector<int> sm0(n,INT_MAX); vector<int> big0(n,0); vector<int> sm1(n,INT_MAX); vector<int> big1(n,0); for(int i = 0; i < n; i++) { int l = -1; for(int j = 0; j < m; j++) { if(haha[i][j] != -1) { if(haha[i][j] == 0) { big0[i] = max(big0[i],j+1); sm0[i] = min(sm0[i],j+1); } else { big1[i] = max(big1[i],j+1); sm1[i] = min(sm1[i],j+1); } } } } int p = -1; for(int i = 0; i < n; i++) { int c = -1; if(sm0[i] == INT_MAX || sm1[i] == INT_MAX) { continue; } if(sm0[i] > big1[i]) { c = 1; } else if(big0[i] < sm1[i]) { c = 0; } else { return false; } if(p != -1 && c != p) { return false; } p = c; } if(p == -1) { return true; } x = m; for(int i = 0; i < n; i++) { int l,r; if(p == 0) { l = big0[i]; r = min(m,sm1[i]-1); } else { l = big1[i]; r = min(m,sm0[i]-1); } if(x < l) { break; } x = min(x,r); if(i == n-1) { return true; } } x = 0; for(int i = 0; i < n; i++) { int l,r; if(p == 0) { l = big0[i]; r = min(m,sm1[i]-1); } else { l = big1[i]; r = min(m,sm0[i]-1); } if(x > r) { break; } x = max(x,l); if(i == n-1) { return true; } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int a; vector<pair<int,pair<int,int>>> bruh(0); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> a; bruh.push_back({a,{i,j}}); } } sort(bruh.begin(),bruh.end()); int sm = bruh[0].first,big = bruh[n*m-1].first; int l = 0,r = 1e9; while(l < r) { int mid = (l+r)/2; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { haha[i][j] = -1; } } haha[bruh[0].second.first][bruh[0].second.second] = 0; for(int i = 1; i < bruh.size(); i++) { if(big-bruh[i].first > mid) { haha[bruh[i].second.first][bruh[i].second.second] = 0; } } for(int i = 0; i < bruh.size(); i++) { if(bruh[i].first-sm > mid) { haha[bruh[i].second.first][bruh[i].second.second] = 1; } } if(check(mid)) { r = mid; } else { l = mid+1; } } cout << l; return 0; }

Compilation message (stderr)

joioi.cpp: In function 'bool check(int)':
joioi.cpp:14:13: warning: unused variable 'l' [-Wunused-variable]
   14 |         int l = -1;
      |             ^
joioi.cpp: In function 'int main()':
joioi.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int i = 1; i < bruh.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
joioi.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int i = 0; i < bruh.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...