Submission #521385

#TimeUsernameProblemLanguageResultExecution timeMemory
521385ivan24Furniture (JOI20_furniture)C++14
0 / 100
4 ms428 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; typedef vector<ii> vii; #define F first #define S second ll min(ll x, ll y){ return ((x < y) ? x : y); } ll max(ll x, ll y){ return ((x > y) ? x : y); } class Grid{ private: ll w,h; vvi c; vii upper_path; // minimize y value vii left_path; // minimize x value bool check (ll x, ll y){ return (h > x && x >= 0 && w > y && y >= 0); } void modify_path(ll x, ll y, vii& path, ll dx, ll dy){ /* cout << "reached: " << x << " " << y << " " << dx << " " << dy << endl; if (c[x+dx][y+dy] == 1){ add(x+dx,y+dy); }else{ path[x+y] = ii(x+dx,y+dy); } c[x][y] = 1; if (check(x-dx,y)) add(x-dx,y); if (check(x,y-dy)) add(x,y-dy); */ while (c[path[x+y].F][path[x+y].S] == 1){ path[x+y].F += dx; path[x+y].S += dy; } ll bdx = max(dx,0), sdx = min(dx,0); ll bdy = max(dy,0), sdy = min(dy,0); for (ll i = x+y-1; i >= 0; i--){ ll diff = abs(path[i+1].F-path[i].F) + abs(path[i+1].F-path[i].F); if (diff == 1) break; ii cd = path[i+1]; cd.F -= bdx; cd.S -= bdy; bool b = check(cd.F,cd.S); if (b) b = b && (c[cd.F][cd.S] == 0); if (b){ path[i] = cd; }else{ cd.F += bdx; cd.S += bdy; cd.F += sdx; cd.S += sdy; path[i] = cd; } } for (ll i = x+y+1; w+h-2 >= i; i++){ ll diff = abs(path[i-1].F-path[i].F) + abs(path[i-1].F-path[i].F); if (diff == 1) break; ii cd = path[i-1]; cd.F -= sdx; cd.S -= sdy; bool b = check(cd.F,cd.S); if (b) b = b && (c[cd.F][cd.S] == 0); if (b){ path[i] = cd; }else{ cd.F += bdx; cd.S += bdy; cd.F += sdx; cd.S += sdy; path[i] = cd; } } } public: Grid(ll _h, ll _w){ w = _w; h = _h; c.assign(h,vi(w,0)); upper_path.resize(w+h-1); left_path.resize(w+h-1); for (ll i = 0; w+h-1 > i; i++){ upper_path[i] = ii(max(0,i-w+1),min(i,w-1)); left_path[i] = ii(min(i,h-1),max(0,i-h+1)); } } ll add (ll x, ll y){ //cout << "called: " << x << " " << y << endl; if (left_path[x+y] == ii(x,y) && upper_path[x+y] == ii(x,y)) return 0; c[x][y] = 1; if (upper_path[x+y] == ii(x,y)) modify_path(x,y,upper_path, 1, -1); if (left_path[x+y] == ii(x,y)) modify_path(x,y,left_path, -1, 1); return 1; } void print(){ cout << "upper_path: \n"; for (auto i: upper_path){ cout << "(" << i.F << " , " << i.S << ") -> "; } cout << endl; cout << "left_path:\n"; for (auto i: left_path){ cout << "(" << i.F << " , " << i.S << ") -> "; } cout << "c:\n"; for (auto i: c){ for (auto j: i) cout << j << " "; cout << endl; } cout << endl; } }; int main(){ ll h,w; cin >> h >> w; Grid grid(h,w); //grid.print(); for (ll i = 0; h > i; i++){ for (ll j = 0; w > j; j++){ ll x; cin >> x; //cout << "added: " << i << " " << j << endl; if (x) grid.add(i,j); } } ll q; cin >> q; //grid.print(); while (q--){ ll x, y; cin >> x >> y; x--; y--; cout << grid.add(x,y) << '\n'; //grid.print(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...