oj.uz

답안 #495944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495944 2021-12-20T08:23:22 Z minhcool Furniture (JOI20_furniture) C++17
0 / 100
 2 ms 1100 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e3 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, m, c[N][N];
set<int> avail[N << 1];// diagonals
 
void prep(){
	avail[n + m].insert(n);
	for(int i = n + m - 1; i >= 2; i--){
		for(int x = max(1LL, i - m); x <= min(i - 1, n); x++){
			int y = i - x;
			if(c[x][y] == 1) continue;
			if(avail[i + 1].find(x) != avail[i + 1].end() || avail[i + 1].find(x + 1) != avail[i + 1].end()) avail[i].insert(x);
		}
	}
	assert(avail[2].size() != 0);
}
 
set<int> er[N << 1];
 
bool upd(int x, int y){
	if(avail[x + y].find(x) == avail[x + y].end()){
		c[x][y] = 1;
		return 1;
	}
	if(avail[x + y].size() == 1) return 0;
	er[x + y].clear();
	er[x + y].insert(x);
	for(int i = x + y; i >= 3; i--){
		if(!er[i].size()) break;
		er[i - 1].clear();
		for(auto tempx : er[i]){
			int tempy = i - tempx;
			// check {tempx - 1, tempy}  
			if(er[i].find(x - 1) != er[i].end() || avail[i].find(x - 1) == avail[i].end()) er[i - 1].insert(tempx - 1);
			// check {tempx, tempy - 1}
			if(er[i].find(x + 1) != er[i].end() || avail[i].find(x + 1) == avail[i].end()) er[i - 1].insert(tempx);
		}
	}
	for(int i = x + y; i >= 2; i--){
		if(!er[i].size()) break;
		for(auto it : er[i]) avail[i].erase(it);
	}
	assert(avail[2].size());
	c[x][y] = 1;
	return 1;
}
 
void process(){
	cin >> n >> m;
    //if(n != 2 || m != 3) return;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++) cin >> c[i][j];
	}
	prep();
    return;
	int q;
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		cout << upd(x, y) << "\n";
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message

furniture.cpp: In function 'bool upd(long long int, long long int)':
furniture.cpp:49:8: warning: unused variable 'tempy' [-Wunused-variable]
   49 |    int tempy = i - tempx;
      |        ^~~~~

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -