Submission #145088

#	Time	Username	Problem	Language	Result	Execution time	Memory
145088		Abelyan	Ili (COI17_ili)	C++17	49 / 100	4014 ms	21240 KiB

ili

#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 / 7
• Subtask 2: 42 / 42
• Subtask 3: 0 / 51