oj.uz

Submission #145085

# Submission time Handle Problem Language Result Execution time Memory
145085 2019-08-18T17:59:14 Z Abelyan Ili (COI17_ili) C++17
0 / 100
 3 ms 892 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;
vector<int> gn[N];
bool col[N];
int main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    cin>>n>>m;
    assert(n<=8);
    FOR(i,n){
        has[i][i]=1;
        ans[i]=2;
    }
    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){
        string a,b;
        cin>>a>>b;
        if (a[0]=='c') g[i][0]=n+(a[1]-'1');
        else g[i][0]=(a[1]-'1');
        if (b[0]=='c') g[i][1]=n+(b[1]-'1');
        else g[i][1]=(b[1]-'1');
        //cout<<g[i][0]<<" "<<g[i][1]<<endl;
        has[i]=has[g[i][0]]|has[g[i][1]];
        //if (ans[g[i][0]]==1 || ans[g[i][1]]==1)ans[i]=1;
        //if (ans[g[i][0]]!=2 && ans[g[i][1]]!=2)ans[i]=ans[g[i][0]]|ans[g[i][1]];
        gn[g[i][0]].ad(i);
        gn[g[i][1]].ad(i);
        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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Incorrect 2 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Incorrect 2 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Incorrect 2 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -