| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 753099 |
2023-06-04T14:49:43 Z |
Username4132 |
Ili (COI17_ili) |
C++14 |
|
68 ms |
47232 KB |
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
const int MAXN=10070;
int n, m, pr[MAXN][2];
bool pb[MAXN][2];
string info, ans;
bitset<MAXN> arr[MAXN], wi[MAXN], wo[MAXN], brr[MAXN], one("1"), zero("0"), nuli, uni, add;
vector<int> upb[MAXN], upt[MAXN];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> info;
ans.assign(m, '?');
forn(i, m){
char c1, c2;
int a1, a2;
cin >> c1 >> a1 >> c2 >> a2;
--a1, --a2;
bitset<MAXN> bi1 = c1=='x'? (one<<a1) : arr[a1];
bitset<MAXN> bi2 = c2=='x'? (one<<a2) : arr[a2];
arr[i]=bi1|bi2;
pb[i][0]=(c1=='x'), pb[i][1]=(c2=='x');
pr[i][0]=a1, pr[i][1]=a2;
((c1=='x')? upb : upt)[a1].PB(i);
((c2=='x')? upb : upt)[a2].PB(i);
}
forn(i, m) if(info[i]=='0') nuli|=arr[i];
nuli=~nuli;
forn(i, m) if(info[i]=='1') uni|=(1<<i);
forn(i, m){
arr[i]&=nuli;
if(arr[i].count()==0) ans[i]='0';
}
dforn(i, m){
wo[i]|=(one<<i);
for(int to:upt[i]) wo[i]|=wo[to];
}
forn(i, n) for(int to:upb[i]) wi[i]|=wo[to];
forn(i, n) if((nuli&(one<<i)).count()==0) wi[i]=~zero;
forn(i, m){
bitset<MAXN> b1 = pb[i][0]? wi[pr[i][0]] : brr[pr[i][0]];
bitset<MAXN> b2 = pb[i][1]? wi[pr[i][1]] : brr[pr[i][1]];
brr[i]=b1&b2;
}
forn(i, m) if(info[i]=='1') add|=brr[i];
forn(i, m) if((add&(one<<i)).count()) ans[i]='1';
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
852 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| 7 |
Correct |
1 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
852 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| 7 |
Correct |
1 ms |
852 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2804 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2644 KB |
Output is correct |
| 13 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
852 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| 7 |
Correct |
1 ms |
852 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2804 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2644 KB |
Output is correct |
| 13 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 15 |
Correct |
38 ms |
23968 KB |
Output is correct |
| 16 |
Correct |
44 ms |
28856 KB |
Output is correct |
| 17 |
Correct |
59 ms |
33280 KB |
Output is correct |
| 18 |
Correct |
61 ms |
40044 KB |
Output is correct |
| 19 |
Correct |
44 ms |
30436 KB |
Output is correct |
| 20 |
Correct |
58 ms |
43892 KB |
Output is correct |
| 21 |
Correct |
68 ms |
47232 KB |
Output is correct |
| 22 |
Correct |
56 ms |
44228 KB |
Output is correct |
| 23 |
Correct |
52 ms |
45688 KB |
Output is correct |
| 24 |
Correct |
53 ms |
45268 KB |
Output is correct |
| 25 |
Correct |
62 ms |
37876 KB |
Output is correct |
| 26 |
Correct |
54 ms |
37500 KB |
Output is correct |
| 27 |
Correct |
57 ms |
37584 KB |
Output is correct |
| 28 |
Correct |
58 ms |
36712 KB |
Output is correct |
| 29 |
Correct |
52 ms |
37112 KB |
Output is correct |
| 30 |
Correct |
55 ms |
37352 KB |
Output is correct |
| 31 |
Correct |
49 ms |
39596 KB |
Output is correct |
| 32 |
Correct |
52 ms |
40740 KB |
Output is correct |
