Submission #123180

#	Time	Username	Problem	Language	Result	Execution time	Memory
123180		miguel	Alternating Current (BOI18_alternating)	C++14	0 / 100	22 ms	2420 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;
int 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});
    }
    //cout<<(1<<0);
    if(n<=15 && m<=15){
        for(int mask=1; mask<(1<<m); mask++){
            //cout<<mask<<"\n";
            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;
                //cout<<(((1<<j)&mask)>0)<<" ";
                //if(mask==1) cout<<a<<" "<<b<<endl;
                if(a<=b){
                    //cout<<"xd";
                    for(int pos=a; pos<=b; pos++) ans1[pos]=(ans1[pos]|(((1<<j)&mask)==0)), ans2[pos]=(ans2[pos]|(((1<<j)&mask)>0));
                }
                else{
                    //cout<<"dx";
                    for(int pos=a; pos<=n; pos++) ans1[pos]=(ans1[pos]|(((1<<j)&mask)==0)), ans2[pos]=(ans2[pos]|(((1<<j)&mask)>0));
                    for(int pos=1; pos<=b; pos++) ans1[pos]=(ans1[pos]|(((1<<j)&mask)==0)), ans2[pos]=(ans2[pos]|(((1<<j)&mask)>0));
                }
            }
            int sum=0; //cout<<endl;
            for(int i=1; i<=n; i++){
                //if(mask==1) cout<<ans1[i]<<" "<<ans2[i]<<endl;
                sum+=(ans1[i]+ans2[i]);
            }
            //cout<<sum<<endl;
            if(sum==2*n){
                for(int i=m-1; i>=0; i--){cout<<(((1<<i)&mask)>0);}
                return 0;
            }
        }
    }
}

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