QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#947732#10124. King's Festivallianhao#AC ✓22ms3712kbC++204.2kb2025-03-22 17:09:472025-03-22 17:09:47

Judging History

This is the latest submission verdict.

  • [2025-03-22 17:09:47]
  • Judged
  • Verdict: AC
  • Time: 22ms
  • Memory: 3712kb
  • [2025-03-22 17:09:47]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

// 检查在当前子集中 cur 中加入 x 是否依然满足:
// 对于任意 a,b in cur ∪ {x},若 a+b 为偶,则 (a+b)/2 不在 cur ∪ {x}。
// 只需要检查与 x 相关的组合即可。
bool validToAdd(int x, const vector<int>& cur) {
    // 检查 x 与已有的每个元素 y:
// 若 (x+y) 为偶,则 (x+y)/2 必不在 cur中。
    for (int y : cur) {
        if ((x + y) % 2 == 0) {
            int mid = (x + y) / 2;
            // 检查 cur 中是否有 mid
            if(find(cur.begin(), cur.end(), mid) != cur.end())
                return false;
        }
    }
    // 检查 x 不能成为已有两个数的中点
    int sz = cur.size();
    for (int i = 0; i < sz; i++) {
        for (int j = i+1; j < sz; j++) {
            if ((cur[i] + cur[j]) % 2 == 0 && (cur[i] + cur[j]) / 2 == x)
                return false;
        }
    }
    return true;
}

// 回溯搜索,在 candidates 数组中寻找一个最大子集(存储为 vector<int>),
// 该子集满足上述“无三项等差”性质
void dfs(int pos, const vector<int>& candidates, vector<int>& cur, vector<int>& best) {
    int n = candidates.size();
    if(pos == n){
        if(cur.size() > best.size()){
            best = cur;
        }
        return;
    }
    // 剪枝:剩余候选数加上当前数目不可能超过 best 的大小时可直接返回
    if(cur.size() + (n - pos) <= best.size()){
        return;
    }
    // 选取当前候选数
    int x = candidates[pos];
    if(validToAdd(x, cur)){
        cur.push_back(x);
        dfs(pos+1, candidates, cur, best);
        cur.pop_back();
    }
    // 不选取当前候选数
    dfs(pos+1, candidates, cur, best);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int N = s.size();
    if(N==1){
        cout<<"1\n#\n";
        return 0;
    }
    // S0:固定已有的灯('#')位置(1-indexed)
    vector<bool> fixedLamp(N+1, false);
    for(int i = 0; i < N; i++){
        if(s[i]=='#'){
            fixedLamp[i+1] = true;
        }
    }

    // 对于非固定位置,我们分别收集奇数和偶数候选
    vector<int> oddCandidates, evenCandidates;
    for(int i = 1; i <= N; i++){
        if(!fixedLamp[i]){
            if(i % 2 == 1)
                oddCandidates.push_back(i);
            else
                evenCandidates.push_back(i);
        }
    }

    // 对每个候选集合,用回溯找出最大无三项等差子集 T
    vector<int> bestOdd, bestEven, cur;
    dfs(0, oddCandidates, cur, bestOdd);
    cur.clear();
    dfs(0, evenCandidates, cur, bestEven);

    // 选择使 T 最大的那一组(如果平手任选)
    bool useOdd = (bestOdd.size() >= bestEven.size());
    // chosenT: 存放所选候选集合中的 indices(它们将没有灯放置)
    unordered_set<int> chosenT;
    if(useOdd){
        for (int x : bestOdd)
            chosenT.insert(x);
    } else {
        for (int x : bestEven)
            chosenT.insert(x);
    }

    // 构造最终放灯的位置 S (1-indexed):
    // 固定已有的灯位置固定;其他位置:
    // 如果该位置非固定且其奇偶性与所选集合匹配且出现在 chosenT 中,则不放灯('.');
    // 否则放灯('#').
    string ans(N, '.');
    int lampCount = 0;
    for (int i = 1; i <= N; i++){
        if(fixedLamp[i]) {
            ans[i-1] = '#';
            lampCount++;
        } else {
            // 判断当前 i 是否属于候选的那一组
            bool inChosenGroup = false;
            if(useOdd && (i % 2 == 1)){
                if(chosenT.count(i)) inChosenGroup = true;
            }
            if(!useOdd && (i % 2 == 0)){
                if(chosenT.count(i)) inChosenGroup = true;
            }
            if(inChosenGroup){
                ans[i-1] = '.';
            } else {
                ans[i-1] = '#';
                lampCount++;
            }
        }
    }

    // 输出:第一行输出最终总灯数(包括固定的)
    cout << lampCount << "\n" << ans << "\n";
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

......

output:

4
.#.###

result:

ok Accepted. Used 4 queens.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

.#.#...

output:

4
.#.###.

result:

ok Accepted. Used 4 queens.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

.....

output:

3
.#.##

result:

ok Accepted. Used 3 queens.

Test #4:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.###.

output:

3
.###.

result:

ok Accepted. Used 3 queens.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#.##

output:

3
.#.##

result:

ok Accepted. Used 3 queens.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#.#.#

output:

4
.#.###

result:

ok Accepted. Used 4 queens.

Test #7:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

#.#.#.

output:

4
#.#.##

result:

ok Accepted. Used 4 queens.

Test #8:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

###...

output:

4
###.#.

result:

ok Accepted. Used 4 queens.

Test #9:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

...###

output:

4
.#.###

result:

ok Accepted. Used 4 queens.

Test #10:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

....

output:

2
.#.#

result:

ok Accepted. Used 2 queens.

Test #11:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

..

output:

1
.#

result:

ok Accepted. Used 1 queens.

Test #12:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

#.

output:

1
#.

result:

ok Accepted. Used 1 queens.

Test #13:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#

output:

1
.#

result:

ok Accepted. Used 1 queens.

Test #14:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

##

output:

2
##

result:

ok Accepted. Used 2 queens.

Test #15:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.

output:

1
#

result:

ok Accepted. Used 1 queens.

Test #16:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

#

output:

1
#

result:

ok Accepted. Used 1 queens.

Test #17:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

...............

output:

11
.#.###.#.######

result:

ok Accepted. Used 11 queens.

Test #18:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.....#####.....

output:

11
.#.#######.#.##

result:

ok Accepted. Used 11 queens.

Test #19:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

#####.....#####

output:

13
######.#.######

result:

ok Accepted. Used 13 queens.

Test #20:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

...#........#..

output:

11
.#.###.#.######

result:

ok Accepted. Used 11 queens.

Test #21:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.....#.....#...

output:

11
.#.###.#.######

result:

ok Accepted. Used 11 queens.

Test #22:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

........................................

output:

31
.#.#######.#.###.#########.#.#####.###.#

result:

ok Accepted. Used 31 queens.

Test #23:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

...#.............................#.....#

output:

31
.#.#######.#.###.#########.#.#####.###.#

result:

ok Accepted. Used 31 queens.

Test #24:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

.........................................

output:

32
.#.###.#.#############.###.#.###.#######.

result:

ok Accepted. Used 32 queens.

Test #25:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

.........#.............#.........#......#

output:

32
.#.#######.#.###.#########.#.#####.###.##

result:

ok Accepted. Used 32 queens.

Test #26:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

##..........######............######.#.##

output:

33
##.#.###.#.#########.#.###.#.############

result:

ok Accepted. Used 33 queens.

Test #27:

score: 0
Accepted
time: 20ms
memory: 3712kb

input:

................................................................

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #28:

score: 0
Accepted
time: 20ms
memory: 3584kb

input:

...............................................................#

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #29:

score: 0
Accepted
time: 19ms
memory: 3584kb

input:

##..............................................................

output:

52
##.#.###.#######.#.###.###############.#####.#.#####.###.#####.#

result:

ok Accepted. Used 52 queens.

Test #30:

score: 0
Accepted
time: 4ms
memory: 3712kb

input:

...#.......#.####.....####.........#.#...##.............##.....#

output:

53
.#.###.#.#########.#.#######################.#.###.#.#########.#

result:

ok Accepted. Used 53 queens.

Test #31:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

################################################################

output:

64
################################################################

result:

ok Accepted. Used 64 queens.

Test #32:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

.......###################......................################

output:

56
.#.###.###################.#.###.#.#########.###################

result:

ok Accepted. Used 56 queens.

Test #33:

score: 0
Accepted
time: 17ms
memory: 3712kb

input:

............................#...................................

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #34:

score: 0
Accepted
time: 19ms
memory: 3712kb

input:

.............................#..................................

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #35:

score: 0
Accepted
time: 19ms
memory: 3584kb

input:

...............................................................

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 50 queens.

Test #36:

score: 0
Accepted
time: 21ms
memory: 3712kb

input:

#..............................................................

output:

51
##.#.###.#######.#.###.###############.#####.#.#####.###.#####.

result:

ok Accepted. Used 51 queens.

Test #37:

score: 0
Accepted
time: 17ms
memory: 3584kb

input:

.#.............................................................

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 50 queens.

Test #38:

score: 0
Accepted
time: 16ms
memory: 3712kb

input:

.............................................................#.

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 50 queens.

Test #39:

score: 0
Accepted
time: 10ms
memory: 3712kb

input:

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 50 queens.

Test #40:

score: 0
Accepted
time: 11ms
memory: 3584kb

input:

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

output:

51
#.#.###.#######.#.###.###############.#####.#.#####.###.#####.#

result:

ok Accepted. Used 51 queens.

Test #41:

score: 0
Accepted
time: 10ms
memory: 3584kb

input:

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

output:

51
#.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 51 queens.

Test #42:

score: 0
Accepted
time: 11ms
memory: 3584kb

input:

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #43:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

...

output:

1
.#.

result:

ok Accepted. Used 1 queens.

Test #44:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

..#

output:

2
.##

result:

ok Accepted. Used 2 queens.

Test #45:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#.

output:

1
.#.

result:

ok Accepted. Used 1 queens.

Test #46:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

#..

output:

2
##.

result:

ok Accepted. Used 2 queens.

Test #47:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.##

output:

2
.##

result:

ok Accepted. Used 2 queens.

Test #48:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

#.#

output:

2
#.#

result:

ok Accepted. Used 2 queens.

Test #49:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

##.

output:

2
##.

result:

ok Accepted. Used 2 queens.

Test #50:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

###

output:

3
###

result:

ok Accepted. Used 3 queens.

Test #51:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

.......

output:

4
.#.###.

result:

ok Accepted. Used 4 queens.

Test #52:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

........

output:

5
.#.###.#

result:

ok Accepted. Used 5 queens.

Test #53:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.........

output:

5
.#.###.#.

result:

ok Accepted. Used 5 queens.

Test #54:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

..........

output:

6
.#.###.#.#

result:

ok Accepted. Used 6 queens.

Test #55:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

...........

output:

7
.#.###.#.##

result:

ok Accepted. Used 7 queens.

Test #56:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

............

output:

8
.#.###.#.###

result:

ok Accepted. Used 8 queens.

Test #57:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

.............

output:

9
.#.###.#.####

result:

ok Accepted. Used 9 queens.

Test #58:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

.###############################################################

output:

63
.###############################################################

result:

ok Accepted. Used 63 queens.

Test #59:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

###############################################################.

output:

63
###############################################################.

result:

ok Accepted. Used 63 queens.

Test #60:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

.....#.#...##...#..#...#.#..##

output:

22
.#.###.#.#########.#.###.#.###

result:

ok Accepted. Used 22 queens.

Test #61:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#.#.###..#...##......#......#.

output:

23
.#.#####.###.#####.#.#####.###.

result:

ok Accepted. Used 23 queens.

Test #62:

score: 0
Accepted
time: 22ms
memory: 3584kb

input:

............................................................#...

output:

51
#.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 51 queens.

Test #63:

score: 0
Accepted
time: 12ms
memory: 3712kb

input:

..................................................#..#..........

output:

51
.#.#####.###.#####.#.#####.###############.###.#.#######.###.#.#

result:

ok Accepted. Used 51 queens.

Test #64:

score: 0
Accepted
time: 14ms
memory: 3712kb

input:

.............#.#....................................#...........

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #65:

score: 0
Accepted
time: 14ms
memory: 3712kb

input:

....................#............#.#....#....................#..

output:

52
.#.###.#.#########.#####.#.###########.###############.#.###.#.#

result:

ok Accepted. Used 52 queens.

Test #66:

score: 0
Accepted
time: 8ms
memory: 3712kb

input:

............#...#.....#......#.#...............#......##........

output:

52
.#.###.#.#########.#.###.###################.#####.#.#####.###.#

result:

ok Accepted. Used 52 queens.

Test #67:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

#.#..##.##.#.#..##.#.#...#...#..#.........#..#.#..#.....##.####.

output:

54
####.#####.#.#####.###.#######.#############.#.#####.#.#########

result:

ok Accepted. Used 54 queens.

Test #68:

score: 0
Accepted
time: 21ms
memory: 3712kb

input:

..............................................................#

output:

51
.#.###.#######.#.###.###############.#####.#.#####.###.#####.##

result:

ok Accepted. Used 51 queens.

Test #69:

score: 0
Accepted
time: 16ms
memory: 3712kb

input:

.....................#............#............................

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 50 queens.

Test #70:

score: 0
Accepted
time: 18ms
memory: 3712kb

input:

......................#....#..............#....................

output:

51
.#.###.#.#########.#.###.#.###########################.#.###.#.

result:

ok Accepted. Used 51 queens.

Test #71:

score: 0
Accepted
time: 9ms
memory: 3584kb

input:

...............#..........#...#............#....#..............

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 50 queens.

Test #72:

score: 0
Accepted
time: 6ms
memory: 3584kb

input:

...#.##...#..........#...............#.......#.....#...........

output:

50
.#.#####.###.#####.#.#####.###############.###.#.#######.###.#.

result:

ok Accepted. Used 50 queens.

Test #73:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

..##....##......#.##.#.#.............##.###.#####...##.#.##...#

output:

51
.###.#.###.#############.#.#######.#.#############.###.#.###.##

result:

ok Accepted. Used 51 queens.

Test #74:

score: 0
Accepted
time: 20ms
memory: 3712kb

input:

..............................................................

output:

50
.#.###.#######.#.###.###############.#####.#.#####.###.#####.#

result:

ok Accepted. Used 50 queens.

Test #75:

score: 0
Accepted
time: 17ms
memory: 3712kb

input:

.............................................................

output:

49
.#.###.#######.#.###.###############.#####.#.#####.###.#####.

result:

ok Accepted. Used 49 queens.

Test #76:

score: 0
Accepted
time: 12ms
memory: 3712kb

input:

............................................................

output:

48
.###.#.#######.#.###.#################.###.#.#######.#.###.#

result:

ok Accepted. Used 48 queens.

Test #77:

score: 0
Accepted
time: 13ms
memory: 3712kb

input:

...........................................................

output:

47
.###.#.#######.#.###.#################.###.#.#######.#.###.

result:

ok Accepted. Used 47 queens.

Test #78:

score: 0
Accepted
time: 12ms
memory: 3584kb

input:

..........................................................

output:

47
.#.###.#######.#.###.###############.#####.#.#####.###.###

result:

ok Accepted. Used 47 queens.

Test #79:

score: 0
Accepted
time: 10ms
memory: 3712kb

input:

.........................................................

output:

46
.#.###.#######.#.###.###############.#####.#.#####.###.##

result:

ok Accepted. Used 46 queens.

Test #80:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

#.#..........#......#.............#...#.#...##.#.........#....#

output:

51
#.#.#####.#.###########.#####.###.#####.###########.#.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #81:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

#.........#.....#.....###...................###..#.....#....#..

output:

51
##.###.#.###.#############.#.#######.#.#############.###.#.###.

result:

ok Accepted. Used 51 queens.

Test #82:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

#.........#.....#.....##....................###..#.....#....#..#

output:

52
##.###.#.###.#############.#.#######.#.#############.###.#.###.#

result:

ok Accepted. Used 52 queens.

Test #83:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

........##.....#.#..................#.#........#....#....####...

output:

52
###.#.#####.#.###########.#####.###.#####.###########.#.#####.#.

result:

ok Accepted. Used 52 queens.

Test #84:

score: 0
Accepted
time: 4ms
memory: 3712kb

input:

#................#.#.#....#............#.#..#.#.........#...#..#

output:

52
#.###.#.###.#############.#.#######.#.#############.###.#.###.##

result:

ok Accepted. Used 52 queens.

Test #85:

score: 0
Accepted
time: 5ms
memory: 3712kb

input:

.#....#......#.###....#.............#...#.#.#.#.................

output:

52
#####.###.#.#######.#.###.#################.###.#.#######.#.###.

result:

ok Accepted. Used 52 queens.

Test #86:

score: 0
Accepted
time: 4ms
memory: 3712kb

input:

###.#...........#.......#.........#....#....##.........##.......

output:

52
###.#####.###.#####.#.#####.###############.###.#.#######.###.#.

result:

ok Accepted. Used 52 queens.

Test #87:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

#.##..#......#......#..##.......#.#...#.#...##.#......#..#....#

output:

51
#.###.#.#######.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #88:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#...#........######...#.#.........#....###.#....##.........#..

output:

51
##.###.#.###.#############.#.#######.#.#############.###.#.###.

result:

ok Accepted. Used 51 queens.

Test #89:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

##...#.........#..#....##.#......#.#....#....#..##..##.#.#.....

output:

51
##.###.#.#######.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 51 queens.

Test #90:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

###.#...........#.......#........##...##....##.....##..###.#...

output:

52
###.#.#####.###.###############.###.#####.#.#####.###.#######.#

result:

ok Accepted. Used 52 queens.

Test #91:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

#.##..#......#......#..##.......#.#...#.#...##.#......#..#....#.

output:

52
#.###.#.#######.###.###############.#####.#.#####.###.#####.#.##

result:

ok Accepted. Used 52 queens.

Test #92:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

#........#.......#.#.#....#.........#.##.#..#.##....#...#..##..#

output:

52
#.###.#.###.#############.#.#######.#.#############.###.#.###.##

result:

ok Accepted. Used 52 queens.

Test #93:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

#.#..........#......#..##.......#.#...#.#...##.#.........#....#

output:

51
#.###.#.#######.###.###############.#####.#.#####.###.#####.#.#

result:

ok Accepted. Used 51 queens.

Test #94:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

#.........#.....#.#...###..#................###..#.....#.#..#..

output:

51
##.###.#.###.#############.#.#######.#.#############.###.#.###.

result:

ok Accepted. Used 51 queens.

Test #95:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

...#...#......#...#.#...........#..#.#....#..##.#..#.........##

output:

51
.###.#.###.#############.#.#######.#.#############.###.#.###.##

result:

ok Accepted. Used 51 queens.

Test #96:

score: 0
Accepted
time: 3ms
memory: 3456kb

input:

##...#.........#..#..............#.#....#....#..##..##.#.#.....

output:

51
##.###.#.#######.###.###############.#####.#.#####.###.#####.#.

result:

ok Accepted. Used 51 queens.

Test #97:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

...........#.##......#..#.#.#..#.....##...#..#..#..#..........#

output:

51
##.###.#.#######.#.###.#################.###.#.#######.#.###.##

result:

ok Accepted. Used 51 queens.

Test #98:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

#.........#.....#.#...##...#................###..#.....#.#..#..#

output:

52
##.###.#.###.#############.#.#######.#.#############.###.#.###.#

result:

ok Accepted. Used 52 queens.

Test #99:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

........##.....#.#......#...........#.#........#..###....####...

output:

52
###.#.#####.#.###########.#####.###.#####.###########.#.#####.#.

result:

ok Accepted. Used 52 queens.

Test #100:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

#........#.......#.#.#....#...........##.#..#.#.....#...#...#..#

output:

52
#.###.#.###.#############.#.#######.#.#############.###.#.###.##

result:

ok Accepted. Used 52 queens.

Test #101:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

.#.#.#....#...######...#.#.........#....###.#....##.........##.

output:

51
##.###.#.###.#############.#.#######.#.#############.###.#.###.

result:

ok Accepted. Used 51 queens.

Test #102:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

.##..##.....######..###........#....#...#.#.###.......#........

output:

52
###.#####.#.###########.#####.###.#####.###########.#.#####.#.#

result:

ok Accepted. Used 52 queens.

Test #103:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

###.#...........#.......#....#...##..###.#..##.....##..###.#...

output:

52
###.#####.###.#####.#.#####.###############.###.#.###.#######.#

result:

ok Accepted. Used 52 queens.

Test #104:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

.#.#.#....#...######...#.#.........#....###.#....##.........##..

output:

52
##.###.#.###.#############.#.#######.#.#############.###.#.###.#

result:

ok Accepted. Used 52 queens.

Test #105:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

###.#...........#.......#....#...##...##.#..##.....##..###.#...#

output:

53
###.#####.###.#####.#.#####.###############.###.#.###.#######.##

result:

ok Accepted. Used 53 queens.

Extra Test:

score: 0
Extra Test Passed