Submission #1122140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122140		dwuy	Alternating Current (BOI18_alternating)	C++14	13 / 100	534 ms	166476 KiB

alternating

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

struct SEG{
    int l, r, id;
    bool operator < (const SEG &o){
        return l != o.l? l < o.l : r < o.r;
    }
};
int n, m;
SEG a[MX];
int ans[MX];
int d[202][202][202];
tpiii trace[202][202][202];

int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
        if(a[i].r < a[i].l) a[i].r += n;
    }

    sort(a + 1, a + 1 + m);
    int delta = a[1].l - 1;
    for(int i=1; i<=m; i++){
        a[i].l -= delta;
        a[i].r -= delta;
    }   

    memset(d, 0x3f, sizeof d);
    const int BB = d[0][0][0];
    d[a[1].r][0][0] = 1;
    for(int i=1; i<=m; i++){
        int l = a[i].l, r = a[i].r;
        for(int p=1; p<=n<<1; p++){
            for(int u=0; u<=n<<1; u++){
                for(int v=u; v<=n<<1; v++) if(d[p][u][v] < i){
                    if(l <= p + 1){
                        d[r][u][v] = min(d[r][u][v], i);
                        if(d[r][u][v] == i) trace[r][u][v] = {p, u, v};
                    }
                    if(min(v, r) - max(l, u) >= -1){
                        int _u = min(l, u);
                        int _v = max(v, r);
                        d[p][_u][_v] = min(d[p][_u][_v], i);
                        if(d[p][_u][_v] == i) trace[p][_u][_v] = {p, u, v};
                    }
                    d[p][l][r] = min(d[p][l][r], i);
                    if(d[p][l][r] == i) trace[p][l][r] = {p, u, v};
                }
            }
        }
    }    
    for(int i=n; i<=n<<1; i++){
        for(int u=1; u<=n<<1; u++){
            for(int v=u+n-1; v<=n<<1; v++){
                if(d[i][u][v] != BB){
                    int x = i, y = u, z = v;
                    while(x != 0 || y != 0 || z != 0){
                        int p = d[x][y][z];
                        int _x, _y, _z;
                        tie(_x, _y, _z) = trace[x][y][z];
                        if(_x != x) ans[a[p].id] = 1;
                        x = _x, y = _y, z = _z;
                    }
                    for(int i=1; i<=m; i++) cout << ans[i];
                    return 0;
                }
            }
        }
    }

    cout << "impossible", exit(0);

    return 0;
}

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