QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51624 | #4632. Card Shark | sealnot123# | TL | 5ms | 8588kb | C++ | 2.0kb | 2022-10-03 03:47:37 | 2022-10-03 03:47:41 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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 ...