제출 #772655

#제출 시각아이디문제언어결과실행 시간메모리
772655Sam_a17Furniture (JOI20_furniture)C++17
0 / 100
2809 ms524288 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int)x.size() #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define blt __builtin_popcount #define pb push_back #define popf pop_front #define popb pop_back #define ld long double #define ll long long void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(long double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} // template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(Tree <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} // for random generations mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // mt19937 myrand(131); // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); // if(str == "input") { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // } else if(str != "") { // freopen((str + ".in").c_str(), "r", stdin); // freopen((str + ".out").c_str(), "w", stdout); // } } const int inf = 1e9; const long long mod = 1e9 + 7; const int N = 1005; int vis1[N][N], vis2[N][N]; int a[N][N]; int n, m, when[1005][1005]; pair<int, int> p[N][N]; int hs[N][N], dp[N][N]; bool don[N][N]; int di[2 * N]; bool check1() { queue<pair<int, int>> q; vector<pair<int, int>> pte; vis1[n][m] = true; q.push({n, m}); int ok = 0; while(!q.empty()) { auto u = q.front(); q.pop(); int x = u.first, y = u.second; if(x - 1 >= 1 && a[x - 1][y] == 0) { if(!vis1[x - 1][y]) { vis1[x - 1][y] = true; q.push({x - 1, y}); } } if(y - 1 >= 1 && a[x][y - 1] == 0) { if(!vis1[x][y - 1]) { vis1[x][y - 1] = true; q.push({x, y - 1}); } } } return ok; } bool check2() { queue<pair<int, int>> q; vector<pair<int, int>> pte; vis2[1][1] = true; q.push({1, 1}); int ok = 0; while(!q.empty()) { auto u = q.front(); q.pop(); int x = u.first, y = u.second; if(x + 1 <= n && a[x + 1][y] == 0) { if(!vis2[x + 1][y]) { vis2[x + 1][y] = true; q.push({x + 1, y}); } } if(y + 1 <= m && a[x][y + 1] == 0) { if(!vis2[x][y + 1]) { vis2[x][y + 1] = true; q.push({x, y + 1}); } } } return ok; } void solve_() { cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> a[i][j]; } } check1(); check2(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(vis1[i][j] && vis2[i][j]) { dp[i][j] = 1; di[i + j]++; } } } int q; cin >> q; vector<pair<int, int>> qr, nqr; for(int i = 1; i <= q; i++) { int x, y; cin >> x >> y; int ok = 1; if(!dp[x][y]) { cout << 1 << '\n'; continue; } if(di[x + y] == 1) { cout << 0 << '\n'; continue; } int cnt = 0; if(x - 1 >= 1 && y + 1 <= m && !dp[x - 1][y + 1]) { cnt++; } if(x + 1 <= n && y - 1 >= 1 && !dp[x + 1][y - 1]) { cnt++; } int ss = x + y - 1; if(cnt == di[ss]) { cout << 0 << '\n'; continue; } queue<pair<int, int>> qq; qq.push({x, y}); dp[x][y] = false; di[x + y]--; while(!qq.empty()) { auto u = qq.front(); qq.pop(); int xi = u.first, yi = u.second; int cnt = 0; if(xi - 1 >= 1 && yi + 1 <= m && !dp[xi - 1][yi + 1]) { dp[xi - 1][yi] = false; di[xi - 1 + yi]--; qq.push({xi - 1, yi}); } if(xi + 1 <= n && yi - 1 >= 1 && !dp[xi + 1][yi - 1]) { dp[xi][yi - 1] = false; di[xi - 1 + yi]--; qq.push({xi, yi - 1}); } } cout << 1 << '\n'; } } int main() { setIO(); auto solve = [&](int test_case)-> void { for(int i = 1; i <= test_case; i++) { solve_(); } }; int test_cases = 1; // cin >> test_cases; solve(test_cases); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

furniture.cpp: In function 'void solve_()':
furniture.cpp:221:11: warning: unused variable 'cnt' [-Wunused-variable]
  221 |       int cnt = 0;
      |           ^~~
furniture.cpp:184:9: warning: unused variable 'ok' [-Wunused-variable]
  184 |     int ok = 1;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...