Submission #123188

#	Time	Username	Problem	Language	Result	Execution time	Memory
123188		miguel	Alternating Current (BOI18_alternating)	C++14	13 / 100	22 ms	1524 KiB

alternating

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll mod = 1000000007;
//#define int ll
int n, m;
vector <pi> w;
bool ans1[16], ans2[16];

int gcd(int a, int b){
    if(a==0) return b;
    else return gcd(b%a, a);
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y;
        cin>>x>>y;
        w.pb({x, y});
    }
    if(n<=15 && m<=15){
        for(int mask=1; mask<(1<<m); mask++){
            for(int j=1; j<=n; j++) ans1[j]=0, ans2[j]=0;
            for(int j=0; j<m; j++){
                int a=w[j].x, b=w[j].y;
                if(a<=b){
                    for(int pos=a; pos<=b; pos++) ans1[pos]=max(ans1[pos], (((1<<j)&mask)==0)), ans2[pos]=max(ans2[pos], (((1<<j)&mask)>0));
                }
                else{
                    for(int pos=a; pos<=n; pos++) ans1[pos]=max(ans1[pos], (((1<<j)&mask)==0)), ans2[pos]=max(ans2[pos], (((1<<j)&mask)>0));
                    for(int pos=1; pos<=b; pos++) ans1[pos]=max(ans1[pos], (((1<<j)&mask)==0)), ans2[pos]=max(ans2[pos], (((1<<j)&mask)>0));
                }
            }
            int sum=0;
            for(int i=1; i<=n; i++){
                //if(mask==5) cout<<i<<" "<<ans1[i]<<" "<<ans2[i]<<endl;
                sum+=(ans1[i]+ans2[i]);
            }
            //cout<<sum<<endl;
            if(sum==2*n){
                for(int i=0; i<m; i++){cout<<(((1<<i)&mask)>0);}
                return 0;
            }
        }
        cout<<"impossible"; return 0;
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26