Submission #370137

#	Time	Username	Problem	Language	Result	Execution time	Memory
370137		Nima_Naderi	Ili (COI17_ili)	C++14	100 / 100	1618 ms	2412 KiB

ili

///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e4 + 10;
ll n, m;
ll cnt[MXN];
char s[MXN], t[MXN];
vector<ll> adj[MXN], adt[MXN];
bool ok0[MXN], ok1[MXN];
bool check(){
    for(int i = n + m; i; i --){
        if(t[i] != '0') continue;
        for(auto j : adt[i]) t[j] = '0';
    }
    for(int i = 1; i <= n; i ++){
        if(t[i] != '0') t[i] = '1';
    }
    for(int i = n + 1; i <= n + m; i ++){
        ll exp = (t[adt[i][0]] == '1') || (t[adt[i][1]] == '1');
        if(t[i] != '?'){
            if(exp && t[i] == '0') return 0;
            if(!exp && t[i] == '1') return 0;
        }
        t[i] = (exp ? '1' : '0');
    }
    return 1;
}
int main(){
    //ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    scanf("%lld%lld", &n, &m);
    scanf("%s", s + n + 1);
    for(int i = 1; i <= n; i ++) s[i] = '?';
    for(int i = n + 1; i <= n + m; i ++){
        char ch; ll id;
        for(int j = 0; j < 2; j ++){
            scanf(" %c", &ch);
            scanf("%lld", &id);
            id += (ch == 'c' ? n : 0);
            adj[id].push_back(i), adt[i].push_back(id);
        }
    }
    /* Input is Ok!
    for(int i = 1; i <= n + m; i ++){
        cout << s[i] << " : ";
        for(auto X : adt[i]) cout << X << ' '; cout << '\n';
    }
    for(int i = 1; i <= n + m; i ++)
        cout << s[i];
    cout << '\n';
    */
    for(int i = n + m; i; i --){
        if(s[i] != '0') continue;
        for(auto j : adt[i]) s[j] = '0';
    }
    for(int i = 1; i <= n + m; i ++){
        if(s[i] != '1') continue;
        for(auto j : adj[i]) s[j] = '1';
    }

    for(int i = 1; i <= n; i ++) cnt[i] = (s[i] == '?');
    for(int i = n + 1; i <= n + m; i ++){
        ok0[i] = ok1[i] = 1;
        for(auto j : adt[i]) cnt[i] += cnt[j];
        if(s[i] == '0') assert(cnt[i] == 0);
        if(s[i] == '?'){
            if(cnt[i] == 0) ok1[i] = 0;
        }
    }
    /*
    memcpy(t, s, n + m + 1);
    for(int i = 1; i <= n + m; i ++)
        cout << t[i];
    cout << '\n';
    for(int i = 1; i <= n + m; i ++)
        cout << s[i];
    cout << '\n';
    return 0;
    */
    for(int i = 1; i <= n + m; i ++){
        if(s[i] != '?') continue;
        memcpy(t, s, n + m + 1);
        t[i] = '0';
        ok0[i] = check();
    }
    for(int i = n + 1; i <= n + m; i ++){
        if(s[i] == '?'){
            if(!ok0[i]) s[i] = '1';
            if(!ok1[i]) s[i] = '0';
        }
        printf("%c", s[i]);
    }
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%lld%lld", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
ili.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%s", s + n + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ili.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |             scanf(" %c", &ch);
      |             ~~~~~^~~~~~~~~~~~
ili.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |             scanf("%lld", &id);
      |             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51