QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#51624#4632. Card Sharksealnot123#TL 5ms8588kbC++2.0kb2022-10-03 03:47:372022-10-03 03:47:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-03 03:47:41]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:8588kb
  • [2022-10-03 03:47:37]
  • 提交

answer

#include<bits/stdc++.h>

#define x first
#define y second
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
#define pb push_back
#define eb emplace_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const int N = 200005;
int mark[N];
vpii g[N];
char s[1000005];
vi ans;
int deg[N];

void dfs(int u) {
    for(auto e : g[u]) {
        if(!mark[e.x]) {
            mark[e.x] = 1;
            dfs(e.y);
            ans.eb(e.x);
        }
    }
}

void solve() {
    int n, m, p;
    bool valid = true;
    scanf("%d %d %d",&n,&m,&p);
    rep(i,0,n){
        scanf(" %s",s);
        vi ones;
        int len = strlen(s);
        rep(j, 0, len) {
            if(s[j] == '1') ones.eb(j);
        }
        if(ones[0] > m-1 || len-ones.back() > m) {
            valid = false;
            continue;
        }
        rep(j, 0, sz(ones)-1) {
            if(ones[j+1]-ones[j] != m) {
                valid = false;
                break;
            }
        }
        if(!valid) continue;
        int a = (m-ones[0]-1)%m;
        int b = len-ones.back()-1;
        g[a].eb(i,b);
        deg[a]++;
        deg[b]--;
    }
    if(!valid) {
        printf("-1\n");
        return ;
    }
    int st = m-p;
    rep(i, 0, m) {
        sort(all(g[i]));
    }

    rep(i, 0, m){
        if(deg[i]) {
            valid = false;
            break;
        }
    }
    if(!valid) {
        printf("-1\n");
        return ;
    }

    dfs(st);
    rep(i, 0, n) {
        if(!mark[i]) {
            valid = false;
            break;
        }
    }

    if(!valid) {
        printf("-1\n");
        return ;
    }

    reverse(all(ans));
    rep(i, 0, n) {
        printf("%d ",ans[i]+1);
    }
    puts("");
}

int main() {
    solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 8432kb

input:

5 4 3
0100010
00100
001000100
0010
0100010

output:

2 1 3 5 4 

result:

ok single line: '2 1 3 5 4 '

Test #2:

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

input:

4 2 1
010
10101
010
10101

output:

2 1 4 3 

result:

ok single line: '2 1 4 3 '

Test #3:

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

input:

1 5 3
001000010000100

output:

1 

result:

ok single line: '1 '

Test #4:

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

input:

2 5 3
01000
00010

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

1 5 3
11111

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

10 5 3
000010000100
0001000010000100001
000100
00010
00010000100
0010
00001000010000100001000010
00010
001
001000010

output:

6 2 1 9 7 3 10 4 8 5 

result:

ok single line: '6 2 1 9 7 3 10 4 8 5 '

Test #7:

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

input:

1000 5 4
010000100
00100
001000
00010000100001000
0010000100
100
00001000010000
000010
00010000100001000010
01000010000100
100
0000100
1
00010000
0010
0001
10000100
00001000
1
000100
0000100001
000010000100001000
00100001
010
00100001000010000100
0000100001
010
00100001000010000100001
0000100001
001...

output:

4 1 2 3 10 5 15 9 14 6 23 7 11 25 28 8 16 12 30 31 13 18 24 20 39 27 34 36 37 21 22 35 47 52 26 29 40 43 44 53 38 17 56 19 42 58 59 60 32 33 57 48 45 65 50 54 71 63 74 41 64 51 73 79 75 80 81 90 62 68 46 70 67 99 87 100 69 108 72 97 76 77 82 83 86 88 49 93 94 98 103 55 101 61 102 106 104 109 105 112...

result:

ok single line: '4 1 2 3 10 5 15 9 14 6 23 7 11...88 984 989 992 994 991 999 998 '

Test #8:

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

input:

1000 5 2
0001000010000100001
00100001
000010
0010000
000100001000
100001000010000100001000010000
010000100001
00010
1000010000100001000
010
010000100001000010
001000
1000010000
000010000100001000
10000
10000100
01000
100001000010
00100
00100
000010000
1000010000100001000010000100001
100
100001000010...

output:

-1

result:

ok single line: '-1'

Test #9:

score: -100
Time Limit Exceeded

input:

100000 5 2
1000010000
1000010
0010000100001
00100
01000010000100001
00010000
10000100
010000
001
010
1000010000
000010000
0000100001000
00100001000
010
1000
10000100
0100
1000
00001000010
01000010000
1
01
001000010000
0000100001
00100001000010
00010000100001
010
0010000100001000010
0010000100
00001
...

output:


result: