oj.uz

답안 #404389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404389 2021-05-14T10:32:31 Z rrrr10000 Alternating Current (BOI18_alternating) C++14
19 / 100
 99 ms 12020 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

int main(){
    ll n,m;cin>>n>>m;
    vp v(m),srt(m);
    vi cnt(n*2+1);
    rep(i,m){
        ll a,b;cin>>a>>b;a--;b--;
        if(a>b)b+=n;
        v[i]=P(a,b);
        srt[i]=P(a,i);
        cnt[a]++;cnt[b+1]--;
    }rep(i,n*2)cnt[i+1]+=cnt[i];rep(i,n)if(cnt[i]+cnt[i+n]<2)dame("impossible");
    sort(all(srt));
    P ma=P(-1,-1);
    vvi g(m);
    vi rui(n*2+1);vp tmp;
    rep(i,m){
        ll id=srt[i].se;
        if(ma.fi<v[id].se){
            chmax(ma,P(v[id].se,id));
            tmp.pb(srt[i]);
        }
        else{
            g[ma.se].pb(id);
            rui[v[id].fi]++;rui[v[id].se+1]--;
        }
    }
    rep(i,n*2)rui[i+1]+=rui[i];
    rep(i,n){
        if(rui[i]||rui[i+n]){
            rui[i]=0;rui[i+n]=0;
        }
        else{
            rui[i]=1;rui[i+n]=1;
        }
    }
    rep(i,n*2)rui[i+1]+=rui[i];
    auto rng=[&](ll l,ll r){
        if(l>r)return 0ll;
        ll res=rui[r];if(l)res-=rui[l-1];
        return res;
    };
    vi ans(m,-1);
    // outvp(tmp);
    if(tmp.size()%2==0){
        rep(i,tmp.size())ans[tmp[i].se]=i%2;
    }
    else{
        ll t=-1;
        rep(i,tmp.size()){
            ll a=v[tmp[i].se].se,b=v[tmp[(i+3)%tmp.size()].se].fi;
            if(i+3>=tmp.size())b+=n;
            if(rng(a+1,b-1)==0)t=(i+2)%tmp.size();
        }
        if(t==-1)dame("impossible");
        rep(i,tmp.size())ans[tmp[(i+t)%tmp.size()].se]=i%2;
    }
    queue<ll> que;
    rep(i,m)if(ans[i]!=-1)que.push(i);
    while(!que.empty()){
        ll t=que.front();que.pop();
        for(ll x:g[t]){
            ans[x]=1-ans[t];que.push(x);
        }
    }
    rep(i,m)cout<<ans[i];cout<<endl;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:101:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             if(i+3>=tmp.size())b+=n;
      |                ~~~^~~~~~~~~~~~
alternating.cpp:3:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    3 | #define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
      |                    ^~~
alternating.cpp:115:5: note: in expansion of macro 'rep'
  115 |     rep(i,m)cout<<ans[i];cout<<endl;
      |     ^~~
alternating.cpp:115:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  115 |     rep(i,m)cout<<ans[i];cout<<endl;
      |                          ^~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB no wires in direction 0 between segments 9 and 9
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB no wires in direction 0 between segments 9 and 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB no wires in direction 0 between segments 9 and 9
13 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 11376 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 32 ms 3420 KB Output is correct
4 Correct 39 ms 7356 KB Output is correct
5 Correct 99 ms 11620 KB Output is correct
6 Correct 64 ms 4940 KB Output is correct
7 Correct 81 ms 10848 KB Output is correct
8 Correct 5 ms 3660 KB Output is correct
9 Correct 4 ms 3276 KB Output is correct
10 Correct 92 ms 12020 KB Output is correct
11 Correct 68 ms 9660 KB Output is correct
12 Correct 79 ms 10524 KB Output is correct
13 Correct 2 ms 1740 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 90 ms 11320 KB Output is correct
16 Correct 32 ms 3404 KB Output is correct
17 Correct 88 ms 11328 KB Output is correct
18 Correct 80 ms 8376 KB Output is correct
19 Correct 6 ms 1996 KB Output is correct
20 Correct 85 ms 10980 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB no wires in direction 0 between segments 9 and 9
13 Halted 0 ms 0 KB -