QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#26525#3016. Flashing FluorescentsHakujitsuAC ✓9ms3836kbC++1.3kb2022-04-07 16:30:052022-04-29 03:54:40

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 03:54:40]
  • 评测
  • 测评结果：AC
  • 用时：9ms
  • 内存：3836kb
查看
  • [2022-04-07 16:30:05]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

void debug_out() {cerr << endl;}
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{
    cerr << " " << H;
    debug_out(T...);
}
#ifndef ONLINE_JUDGE
    #define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    int target = 0;
    for (int i = 0; i < n; i += 1) {
        target += (s[i] == '0') << i;
    }
    vector<int> dp(1 << n);
    dp[0] = 1;
    int o = 0;
    for (; !dp[target]; o += 1) {
        auto new_dp = dp;
        for (int mask = 0; mask < (1 << n); mask += 1) {
            if(dp[mask] == 0) continue;
            //debug(o, mask);
            int new_mask = mask;
            
            for (int i = 0; i <= o; i += 1) {
                new_mask ^= 1 << i;    
            }
            for (int i = 0; i < n; i += 1) {
                
                new_dp[new_mask] = max(new_dp[new_mask], dp[mask]);
                new_mask ^= 1 << i;
                if(i + o + 1 < n) new_mask ^= 1 << i + o + 1;
            }
        }
        swap(dp, new_dp);
    }
    cout << o << "\n";
    return 0;
}
源文件, 语言: C++

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

1101

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

1

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

000

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

0

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

1

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

00

output:

2

result:

ok 1 number(s): "2"

Test #7:

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

input:

01

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

10

output:

1

result:

ok 1 number(s): "1"

Test #9:

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

input:

11

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

000

output:

2

result:

ok 1 number(s): "2"

Test #11:

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

input:

001

output:

2

result:

ok 1 number(s): "2"

Test #12:

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

input:

010

output:

2

result:

ok 1 number(s): "2"

Test #13:

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

input:

011

output:

1

result:

ok 1 number(s): "1"

Test #14:

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

input:

100

output:

2

result:

ok 1 number(s): "2"

Test #15:

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

input:

101

output:

1

result:

ok 1 number(s): "1"

Test #16:

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

input:

110

output:

1

result:

ok 1 number(s): "1"

Test #17:

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

input:

111

output:

0

result:

ok 1 number(s): "0"

Test #18:

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

input:

0000

output:

3

result:

ok 1 number(s): "3"

Test #19:

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

input:

0001

output:

2

result:

ok 1 number(s): "2"

Test #20:

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

input:

0010

output:

2

result:

ok 1 number(s): "2"

Test #21:

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

input:

0011

output:

2

result:

ok 1 number(s): "2"

Test #22:

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

input:

0100

output:

2

result:

ok 1 number(s): "2"

Test #23:

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

input:

0101

output:

3

result:

ok 1 number(s): "3"

Test #24:

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

input:

0110

output:

2

result:

ok 1 number(s): "2"

Test #25:

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

input:

0111

output:

1

result:

ok 1 number(s): "1"

Test #26:

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

input:

1000

output:

2

result:

ok 1 number(s): "2"

Test #27:

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

input:

1001

output:

2

result:

ok 1 number(s): "2"

Test #28:

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

input:

1010

output:

2

result:

ok 1 number(s): "2"

Test #29:

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

input:

1011

output:

1

result:

ok 1 number(s): "1"

Test #30:

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

input:

1100

output:

2

result:

ok 1 number(s): "2"

Test #31:

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

input:

1101

output:

1

result:

ok 1 number(s): "1"

Test #32:

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

input:

1110

output:

1

result:

ok 1 number(s): "1"

Test #33:

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

input:

1111

output:

0

result:

ok 1 number(s): "0"

Test #34:

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

input:

00000

output:

3

result:

ok 1 number(s): "3"

Test #35:

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

input:

00001

output:

3

result:

ok 1 number(s): "3"

Test #36:

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

input:

00010

output:

3

result:

ok 1 number(s): "3"

Test #37:

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

input:

00011

output:

2

result:

ok 1 number(s): "2"

Test #38:

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

input:

00100

output:

3

result:

ok 1 number(s): "3"

Test #39:

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

input:

00101

output:

2

result:

ok 1 number(s): "2"

Test #40:

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

input:

00110

output:

2

result:

ok 1 number(s): "2"

Test #41:

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

input:

00111

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

01000

output:

3

result:

ok 1 number(s): "3"

Test #43:

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

input:

01001

output:

2

result:

ok 1 number(s): "2"

Test #44:

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

input:

01010

output:

3

result:

ok 1 number(s): "3"

Test #45:

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

input:

01011

output:

3

result:

ok 1 number(s): "3"

Test #46:

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

input:

01100

output:

2

result:

ok 1 number(s): "2"

Test #47:

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

input:

01101

output:

3

result:

ok 1 number(s): "3"

Test #48:

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

input:

01110

output:

2

result:

ok 1 number(s): "2"

Test #49:

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

input:

01111

output:

1

result:

ok 1 number(s): "1"

Test #50:

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

input:

10000

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

10001

output:

2

result:

ok 1 number(s): "2"

Test #52:

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

input:

10010

output:

2

result:

ok 1 number(s): "2"

Test #53:

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

input:

10011

output:

2

result:

ok 1 number(s): "2"

Test #54:

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

input:

10100

output:

2

result:

ok 1 number(s): "2"

Test #55:

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

input:

10101

output:

3

result:

ok 1 number(s): "3"

Test #56:

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

input:

10110

output:

2

result:

ok 1 number(s): "2"

Test #57:

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

input:

10111

output:

1

result:

ok 1 number(s): "1"

Test #58:

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

input:

11000

output:

2

result:

ok 1 number(s): "2"

Test #59:

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

input:

11001

output:

2

result:

ok 1 number(s): "2"

Test #60:

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

input:

11010

output:

2

result:

ok 1 number(s): "2"

Test #61:

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

input:

11011

output:

1

result:

ok 1 number(s): "1"

Test #62:

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

input:

11100

output:

2

result:

ok 1 number(s): "2"

Test #63:

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

input:

11101

output:

1

result:

ok 1 number(s): "1"

Test #64:

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

input:

11110

output:

1

result:

ok 1 number(s): "1"

Test #65:

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

input:

11111

output:

0

result:

ok 1 number(s): "0"

Test #66:

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

input:

1111101111111000

output:

3

result:

ok 1 number(s): "3"

Test #67:

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

input:

1111110000000000

output:

4

result:

ok 1 number(s): "4"

Test #68:

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

input:

1111110000000010

output:

4

result:

ok 1 number(s): "4"

Test #69:

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

input:

1111101101100100

output:

4

result:

ok 1 number(s): "4"

Test #70:

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

input:

1111100010101100

output:

4

result:

ok 1 number(s): "4"

Test #71:

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

input:

1100100010100000

output:

5

result:

ok 1 number(s): "5"

Test #72:

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

input:

1011001000010001

output:

4

result:

ok 1 number(s): "4"

Test #73:

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

input:

1111111111111111

output:

0

result:

ok 1 number(s): "0"

Test #74:

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

input:

1011111111111111

output:

1

result:

ok 1 number(s): "1"

Test #75:

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

input:

1011111111000111

output:

3

result:

ok 1 number(s): "3"

Test #76:

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

input:

0000000000000000

output:

6

result:

ok 1 number(s): "6"

Test #77:

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

input:

1111111111101010

output:

3

result:

ok 1 number(s): "3"

Test #78:

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

input:

1111111101110101

output:

4

result:

ok 1 number(s): "4"

Test #79:

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

input:

1111111100110000

output:

3

result:

ok 1 number(s): "3"

Test #80:

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

input:

1111111010101010

output:

5

result:

ok 1 number(s): "5"

Test #81:

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

input:

1111110010101010

output:

5

result:

ok 1 number(s): "5"

Test #82:

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

input:

1111101010101010

output:

6

result:

ok 1 number(s): "6"

Test #83:

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

input:

1111011010101010

output:

6

result:

ok 1 number(s): "6"

Test #84:

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

input:

1111010110101010

output:

6

result:

ok 1 number(s): "6"

Test #85:

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

input:

0010101010101010

output:

8

result:

ok 1 number(s): "8"

Test #86:

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

input:

1010101010101101

output:

8

result:

ok 1 number(s): "8"

Test #87:

score: 0
Accepted
time: 7ms
memory: 3692kb

input:

1010101010111010

output:

7

result:

ok 1 number(s): "7"

Test #88:

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

input:

1011010101010101

output:

8

result:

ok 1 number(s): "8"

Test #89:

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

input:

1110101010101010

output:

7

result:

ok 1 number(s): "7"

Test #90:

score: 0
Accepted
time: 7ms
memory: 3704kb

input:

1010101001010100

output:

7

result:

ok 1 number(s): "7"

Test #91:

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

input:

00000010111

output:

4

result:

ok 1 number(s): "4"

Test #92:

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

input:

11111111010

output:

2

result:

ok 1 number(s): "2"
English 繁體中文 简体中文

服务器时间: 2024-11-29 20:40:37 | 开源项目