Submission #1129052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129052		Ludissey	Alternating Current (BOI18_alternating)	C++20	13 / 100	19 ms	4932 KiB

alternating

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m; cin >> n >> m;
    vector<pair<pair<int,int>,int>> edge1(m);
    vector<pair<pair<int,int>,int>> edge(m);
    vector<bool> c(m);
    for (int i = 0; i < m; i++)
    {
        int a,b; cin >> a >> b;
        if(b<a) b+=n;
        edge[i]={{a,b},i};
    }
    sort(all(edge));
    bool b=false;    
    for (int x = 0; x < (1<<m); x++)
    {
        int e=-100;
        int s=-1;
        int e2=-100;
        int s2=-1;
        for (int j = 0; j < m; j++) c[j]=(bool)(x&(1<<j));
        for (int i = 0; i < m; i++)
        {
            if(c[edge[i].second]==1) {
                if(s==-1) { s=edge[i].first.first; e=edge[i].first.second; }
                else if(e>=edge[i].first.first-1) {
                    e=max(e,edge[i].first.second);
                }
            }
        }
        for (int i = 0; i < m; i++)
        {
            if(c[edge[i].second]==0) {
                if(s2==-1) { s2=edge[i].first.first; e2=edge[i].first.second; }
                else if(e2>=edge[i].first.first-1) e2=max(e2,edge[i].first.second);
            }
        }
        bool b2=false;
        if(e>=s+n-1&&e2>=s2+n-1) b2=true;
        else b2=false;
        if(b2){
            for (int i = 0; i < m; i++)
            {
                cout << c[i];
            }
            b=true;
            break;
        }

    }
    if(b==false) cout << "impossible\n";
    return 0;
}

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