oj.uz

답안 #391069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391069 2021-04-17T18:55:52 Z Redhood Alternating Current (BOI18_alternating) C++14
0 / 100
 3000 ms 2464 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 296 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 296 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 296 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 2464 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 31 ms 1448 KB Output is correct
4 Correct 34 ms 1444 KB Output is correct
5 Execution timed out 3086 ms 2424 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 296 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -