Submission #391069

#	Time	Username	Problem	Language	Result	Execution time	Memory
391069		Redhood	Alternating Current (BOI18_alternating)	C++14	0 / 100	3086 ms	2464 KiB

alternating

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
const int inf = 1e9;
int main(){
    int n , m;
    cin >> n >> m;
    vector < pair < int , int > > lines(m);
    for(int i = 0 ; i < m; ++i){
        int l , r;
        cin >> l >> r;
        lines[i] = {l , r};
    }
    vector < bool > used(m);
    vector < int > answer(m);
    /// try to do it
    auto get_len = [&n](pair < int , int > line){
        int cur_len = (line.se + n - line.fi) + 1;
        if(cur_len > n)
            cur_len -= n;
        return cur_len;
    };
    auto move_seg = [&n](int &seg){
        seg++;
        if(seg == n + 1)
            seg = 1;
    };
    auto come_through = [&lines, &n](int id , int seg){
        if(lines[id].first <= lines[id].second){
            if(seg >= lines[id].first && seg <= lines[id].second)
                return true;
            else
                return false;
        }
        if(seg >= lines[id].first && seg <= n)
            return true;
        if(seg >= 1 && seg <= lines[id].second)
            return true;
        return false;
    };

//    cerr << " LENS \n";
//    for(int i = 0 ; i  < m; ++i)
//        cerr << get_len(lines[i]) << ' ';
//    cerr << '\n';
    auto tryy = [&](int type){
        int best_len = -1 , best_line = -1;
        for(int i = 0; i < m; ++i){
            if(used[i])
                continue;
            int cur_len = get_len(lines[i]);
            if(best_len < cur_len){
                best_len = cur_len;
                best_line = i;
            }
        }
        if(best_line == -1)
            return false;
        int done = 0;
        done += get_len(lines[best_line]);
        vector < bool > segments_done(n + 1);

        used[best_line] = 1;
        answer[best_line] = type;
        int seg = lines[best_line].first;
        for(int it = 0; it < done; ++it){
            segments_done[seg] = 1;
            move_seg(seg);
        }
        while(done < n){
            while(segments_done[seg]){
                move_seg(seg);
            }
//            cerr << " done " << done << '\n';
            int cur_best_line = -1 , cur_best_val = inf;
            for(int x = 0 ; x < m; ++x){
                if(used[x])
                    continue;
                if(come_through(x , seg)){
                    int val = 0;
                    int po_seg = lines[x].fi;
                    for(int it = 0 ; it < get_len(lines[x]); ++it){
                        if(segments_done[po_seg])
                            val++;
                        move_seg(po_seg);
                    }
                    if(val < cur_best_val){
                        cur_best_val = val;
                        cur_best_line = x;
                    }
                }
            }
            /// use it
////            cerr << done << '\n';
            if(cur_best_line == -1)
                return false;
            int po_seg = lines[cur_best_line].fi;
            for(int it = 0 ; it < get_len(lines[cur_best_line]); ++it){
                if(!segments_done[po_seg])
                    done++ , segments_done[po_seg] = 1;
                move_seg(po_seg);
            }
            used[cur_best_line] = 1;
            answer[cur_best_line] = type;
        }
//        for(int i = 0 ;  i < m; ++i)
//            cerr << used[i] << ' ';
//        cerr << '\n';
//        cerr << done << endl;
        return true;
    };
//    cerr << tryy(0) << endl;
//    cerr << tryy(1) << endl;
    if(!tryy(0) || !tryy(1))
        cout << "impossible\n";
    else{
        for(int i = 0 ; i < m; ++i)
            cout << answer[i];
    }
    return 0;
}

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