Submission #1170590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170590		Zero_OP	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	320 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl =pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;

using vpi = vector<pi>;
using vpl = vector<pl>;

//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().cout());
//ll random(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); }

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
      if(fopen("B.inp", "r")){
            freopen("B.inp", "r", stdin);
            freopen("B.out", "w", stdout);
      }
}

const int MAX = 1e6 + 5;
const int mod = 1e9 + 7;

struct mint{
      int v;
      mint(int v = 0) : v(v) {}

      mint& operator += (const mint& o){
            v += o.v;
            if(v >= mod) v -= mod;
            return *this;
      }

      mint& operator -= (const mint& o){
            v -= o.v;
            if(v < 0) v += mod;
            return *this;
      }

      mint& operator *= (const mint& o){
            v = 1LL * v * o.v % mod;
            return *this;
      }

      friend mint operator + (mint a, const mint& b){ return a += b; }
      friend mint operator - (mint a, const mint& b){ return a -= b; }
      friend mint operator * (mint a, const mint& b){ return a *= b; }

      friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
      friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }

      friend ostream& operator << (ostream& out, const mint& o){ return out << o.v; }
};

int N;
pi segments[MAX];

bool can_put(int i, int j){
      return (segments[i].ff < segments[j].ff && segments[i].ss > segments[j].ss) || (segments[i].ss < segments[j].ff);
}

namespace subtask1{
      bool check(){
            return N <= 20;
      }

      void solve(){
            int cnt = 0;
            for(int mask = 0; mask < (1 << N); ++mask){
                  vi A, B;
                  FOR(i, 0, N){
                        if(mask >> i & 1){
                              A.pb(i+1);
                        } else B.pb(i+1);
                  }

                  bool ok = true;
                  FOR(i, 1, sz(A)){
                        FOR(j, 0, i){
                              ok &= can_put(A[j], A[i]);
                        }
                  }

                  FOR(i, 1, sz(B)){
                        FOR(j, 0, i){
                              ok &= can_put(B[j], B[i]);
                        }
                  }

                  if(ok){
                        ++cnt;
                        cout << bitset<8>(mask) << '\n';
                  }
            }
            cout << cnt << '\n';
      }
}

namespace subtask12{
      bool check(){
            return N <= 2000;
      }

      bool vis[2003];
      vi adj[2003];
      int color[MAX];

      void solve(){
            int cnt = 0;
            FOR(i, 1, N+1){
                  FOR(j, i+1, N+1){
                        if(segments[j].ff < segments[i].ss && segments[i].ss < segments[j].ss) {
                              adj[i].pb(j);
                              adj[j].pb(i);
                              ++cnt;
//                              cout << i << ' ' << j << '\n';
                        }
                  }


            }

            cout << cnt << '\n';
//            assert(cnt <= 2 * N);

            mint ans = 1;
            FOR(i, 1, N+1){
                  if(vis[i]) continue;
                  queue<int> q;
                  q.push(i);
                  vis[i] = true;

//                  cout << dbg(i) << '\n';

                  while(!q.empty()){
                        int u = q.front(); q.pop();
                        for(auto v : adj[u]){
                              if(!vis[v]){
                                    color[v] = color[u] ^ 1;
                                    q.push(v);
                                    vis[v] = true;
                              } else if(color[u] == color[v]){
                                    cout << 0 << '\n';
                                    return;
                              }
                        }
                  }

                  ans += ans;
            }
            cout << ans << '\n';
      }
}


int main(){
      setIO();

      cin >> N;
      FOR(i, 1, N+1){
            cin >> segments[i].ff >> segments[i].ss;
      }

      sort(segments+1, segments + N+1);

//      if(subtask1::check()) return subtask1::solve(), 0;
      if(subtask12::check()) return subtask12::solve(), 0;
//      subtask34::solve();

      return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void setIO()':
port_facility.cpp:56:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |             freopen("B.inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:57:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |             freopen("B.out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22