QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207947 | #6644. Red Black Grid | UFRJ# | TL | 0ms | 3572kb | C++14 | 3.9kb | 2023-10-09 00:43:05 | 2023-10-09 00:43:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
bool guloso(vector<vector<int>> &grid, int n, int k){
auto isColor = [&](int i, int j, int c) -> bool {
if(i < 0 || i >= n) return false;
if(j < 0 || j >= n) return false;
if(grid[i][j] == c) return true;
return false;
};
using T = tuple<int, int, int>; // qtd dif, i, j
array<int, 5> qtd = {0};
int tot = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j<n; j++){
if(grid[i][j]){
tot += isColor(i-1, j, 0);
tot += isColor(i+1, j, 0);
tot += isColor(i, j-1, 0);
tot += isColor(i, j+1, 0);
} else {
int cur = 0;
cur += isColor(i-1, j, 1);
cur += isColor(i+1, j, 1);
cur += isColor(i, j-1, 1);
cur += isColor(i, j+1, 1);
qtd[cur]++;
}
}
}
if(k > tot) return false;
int dif = tot - k;
vector<bool> dp(dif + 1);
vector<pair<int, int>> link(dif + 1, {-1, -1});
dp[0] = 1;
for(int i = 1; i <= 4; i++){
for(int j = dif - i; j >=0 ; j--){
if(!dp[j]) continue;
int k = qtd[i], s = j + i;
while(k > 0 && s <= dif && !dp[s]){
dp[s] = 1, --k, link[s] = {k, i}, s += i;
}
}
}
if(dp[dif]){
vector<int> change(5);
int j = dif;
while(j > 0){
auto [cur, i] = link[j];
//cout<<j<<" "<<cur<<" "<<i<<"\n";
change[i] += cur;
j = j - cur * i;
}
for(int i = 0; i<n; i++){
for(int j = 0; j< n; j++){
if(!grid[i][j]){
int cur = 0;
cur += isColor(i-1, j, 1);
cur += isColor(i+1, j, 1);
cur += isColor(i, j-1, 1);
cur += isColor(i, j+1, 1);
if(change[cur] > 0){
grid[i][j] = 1;
//cout<<"mudei "<<i<<" "<<j<<" "<<cur<<" "<<change[cur]<<"\n";
change[cur]--;
}
}
}
}
return true;
}
return false;
}
void solve(){
int n, k;
cin>>n>>k;
if(n == 1){
cout<<"Possible\n";
cout<<"R\n";
return;
}
if(k == 1 || k == n * (n-1)/2 - 1){
cout<<"Impossible\n";
return;
}
else if(n == 3 && k == 5){
cout<<"Possible\n";
cout<<"RRR\n";
cout<<"RBB\n";
cout<<"RRR\n";
}
else {
vector<vector<int>> grid(n, vector<int>(n));
for(int i = 0; i<n; i++){
for(int j = (i%2); j < n; j += 2){
grid[i][j] = 1;
}
}
if(guloso(grid, n, k)){
cout<<"Possible\n";
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(grid[i][j]) cout<<"B";
else cout<<"R";
}
cout<<"\n";
}
return;
}
grid = vector<vector<int>>(n, vector<int>(n));
for(int i = 0; i<n; i++){
for(int j = !(i%2); j < n; j += 2){
grid[i][j] = 1;
}
}
if(guloso(grid, n, k)){
cout<<"Possible\n";
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(grid[i][j]) cout<<"B";
else cout<<"R";
}
cout<<"\n";
}
return;
}
cout<<"Impossible\n";
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t; cin>>t;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
2 3 6 3 1
output:
Possible BBB BBR BRB Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
4424 1 0 2 4 2 3 2 2 2 1 2 0 3 12 3 11 3 10 3 9 3 8 3 7 3 6 3 5 3 4 3 3 3 2 3 1 3 0 4 24 4 23 4 22 4 21 4 20 4 19 4 18 4 17 4 16 4 15 4 14 4 13 4 12 4 11 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 4 1 4 0 5 40 5 39 5 38 5 37 5 36 5 35 5 34 5 33 5 32 5 31 5 30 5 29 5 28 5 27 5 26 5 25 5 24 5 23 5 22 5 21 5...