Submission #322461

#TimeUsernameProblemLanguageResultExecution timeMemory
322461SeanliuThe Kingdom of JOIOI (JOI17_joioi)C++17
60 / 100
4050 ms72216 KiB
#pragma gcc optimize ("O3") #include <iostream> #include <algorithm> #include <utility> #include <vector> #include <bitset> #include <unordered_map> #define ericxiao ios_base::sync_with_stdio(0);cin.tie(0); #define pii pair<int,int> #define F first #define S second #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) using namespace std; const int maxN = 2e3 + 326, INF = 2e9 + 326; int N, M, arr[maxN][maxN], sz, ii, jj; vector<int> lisan; unordered_map<int, short> cnt; unordered_map<int, vector<pair<short,short>>> pos; bitset<maxN> vis[maxN]; inline char readchar() { static const size_t bufsize = 65536; static char buf[bufsize]; static char *p = buf, *end = buf; if (p == end) end = buf + fread(buf, 1, bufsize, stdin), p = buf; return *p++; } inline void const Read(int & p) { p = 0; int tmp = 0; char c = readchar(); tmp = !(c^'-'); while (c < '0' || c > '9') { c = readchar(); } while (c >= '0' && c <= '9') p = (p<<3)+(p<<1)+(c^48), c = readchar(); p = tmp?-p:p; } inline void take(const short &y, const short &x, int &mx, int &mn, int &d){ if(d == 0){ for(ii = y; ii >= 0 && !vis[ii][x]; ii--){ for(jj= x; jj >= 0 && !vis[ii][jj]; jj--){ vis[ii][jj] = true; cnt[arr[ii][jj]]--; mx = max(mx, arr[ii][jj]); mn = min(mn, arr[ii][jj]); } } } else if(d == 1){ for(ii = y; ii < N && !vis[ii][x]; ii++){ for(jj= x; jj >= 0 && !vis[ii][jj]; jj--){ vis[ii][jj] = true; cnt[arr[ii][jj]]--; mx = max(mx, arr[ii][jj]); mn = min(mn, arr[ii][jj]); } } } else if(d == 2){ for(ii = y; ii < N && !vis[ii][x]; ii++){ for(jj= x; jj < M && !vis[ii][jj]; jj++){ vis[ii][jj] = true; cnt[arr[ii][jj]]--; mx = max(mx, arr[ii][jj]); mn = min(mn, arr[ii][jj]); } } } else if(d == 3){ for(ii = y; ii >= 0 && !vis[ii][x]; ii--){ for(jj= x; jj < M && !vis[ii][jj]; jj++){ vis[ii][jj] = true; cnt[arr[ii][jj]]--; mx = max(mx, arr[ii][jj]); mn = min(mn, arr[ii][jj]); } } } } inline void rot(){ for(ii = 0; ii < sz; ii++){ cnt[ii] = 0; } for(ii = 0; ii < N; ii++) for(jj = 0; jj < M; jj++) { vis[ii].reset(); cnt[arr[ii][jj]]++; } } int main(){ Read(N); Read(M); for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ Read(arr[i][j]); lisan.push_back(arr[i][j]); } } sort(lisan.begin(), lisan.end()); sz = unique(lisan.begin(), lisan.end()) - lisan.begin(); cnt.reserve(sz); pos.reserve(sz); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){ cnt[arr[i][j]]++; if(!pos.count(arr[i][j])){ pos[arr[i][j]] = vector<pair<short,short>>(); //cout << "hello" << arr[i][j] << endl; } pos[arr[i][j]].emplace_back(i, j); } int ans = lisan[sz - 1] - lisan[0]; for(int jizz = 0; jizz < 4; jizz++){ //cout << "in jizz = " << jizz << endl; int mx = -INF, mn = INF, f = 0, e = sz - 1; for(int i = 0; i < sz; i++){ //take all of them // //cout << "i = " << i << ", = " << lisan[i] << endl; for(auto &[y, x] : pos[lisan[i]]){ take(y, x, mx, mn, jizz); } /* for(int y = 0; y < N; y++) for(int x = 0; x < M; x++){ cout << vis[y][x] << " \n"[x == M - 1]; } */ while(f < sz - 1 && !cnt[lisan[f]]) f++; while(e && !cnt[lisan[e]]) e--; if(f == sz || !e) break; ans = min(ans, max(lisan[e] - lisan[f], mx - mn)); //cout << "ans = " << ans << endl; } rot(); } cout << ans << '\n'; }

Compilation message (stderr)

joioi.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize ("O3")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...