oj.uz

Submission #145088

# Submission time Handle Problem Language Result Execution time Memory
145088 2019-08-18T18:14:50 Z Abelyan Ili (COI17_ili) C++17
49 / 100
 4000 ms 21240 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=2e4+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
 
int g[N][2],ans[N];
bitset<N> has[N],zro,nz;
bool col[N];

int n,m;
int get(){
    char c;
    cin>>c;
    int k;
    cin>>k;
    //cout<<c<<" "<<k<<endl;
    if (c=='c')return n+k-1;
    return k-1;
}

int main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    
    cin>>n>>m;
    //assert(n<=8);
    FOR(i,n){
        has[i][i]=1;
    }
    FORT(i,n,n+m-1){
        char c;
        cin>>c;
        ans[i]=2;
        if (c=='1')ans[i]=1;
        if (c=='0')ans[i]=0;
    }
    
    FORT(i,n,n+m-1){
        g[i][0]=get();
        g[i][1]=get();
        //cout<<g[i][0]<<" "<<g[i][1]<<endl;
        has[i]=has[g[i][0]]|has[g[i][1]];
        if (ans[i]==0)zro|=has[i];
    }
    zro.flip();
    FORT(i,n,n+m-1){
        has[i]&=zro;
    }
    FORT(i,n,n+m-1){
        if (ans[i]==2){
            if (has[i].count()==0){
                ans[i]=0;
                continue;
            }
            FORT(j,n,n+m-1){
                if (j==i)continue;
                if ((has[i]&has[j])==has[j] && ans[j]==1){
                    ans[i]=1;
                    break;
                }
            }
        }
        
    }
    
    FORT(i,n,n+m-1){
        if (ans[i]!=2)cout<<(char)(ans[i]+'0');
        else cout<<'?';
    }
    
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 22 ms 1784 KB Output is correct
9 Correct 35 ms 1528 KB Output is correct
10 Correct 24 ms 2040 KB Output is correct
11 Correct 33 ms 1912 KB Output is correct
12 Correct 13 ms 1912 KB Output is correct
13 Correct 16 ms 1912 KB Output is correct
14 Correct 28 ms 1784 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 22 ms 1784 KB Output is correct
9 Correct 35 ms 1528 KB Output is correct
10 Correct 24 ms 2040 KB Output is correct
11 Correct 33 ms 1912 KB Output is correct
12 Correct 13 ms 1912 KB Output is correct
13 Correct 16 ms 1912 KB Output is correct
14 Correct 28 ms 1784 KB Output is correct
15 Correct 482 ms 16656 KB Output is correct
16 Execution timed out 4014 ms 21240 KB Time limit exceeded
17 Halted 0 ms 0 KB -