oj.uz

Submission #123185

# Submission time Handle Problem Language Result Execution time Memory
123185 2019-06-30T10:07:37 Z miguel Alternating Current (BOI18_alternating) C++14
0 / 100
 22 ms 1524 KB 
#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==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;
            }
        }
        cout<<"impossible"; return 0;
    }
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB no wires in direction 0 between segments 11 and 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB no wires in direction 0 between segments 11 and 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB no wires in direction 0 between segments 11 and 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1524 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB no wires in direction 0 between segments 11 and 11
4 Halted 0 ms 0 KB -