Submission #228466

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228466	2020-05-01T05:25:37 Z	caoash	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	Compilation error	0 ms	0 KB

skyscraper

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef pair<int, pi> pii;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define fax(i, a) for (int i = 0; i < (a); i++)
#define f0x(i, a, b) for (int i = (a); i < (b); i++)
#define f0xd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define faxd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define memeset memset
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
 
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
 
namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
 
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class T, class... Ts> void re(T& t, Ts&... ts) { 
        re(t); re(ts...); 
    }
 
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { fax(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { fax(i,SZ) re(a[i]); }
}
 
using namespace input;
 
namespace output {
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T> void pr(const T& x);
    
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
        pr(t); pr(ts...); 
    }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void pr(const T& x) { 
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
        pr("}");
    }
    
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
    }
    
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
    }
    #define dbg(x...) pr("[",#x,"] = ["), pc(x);
}
 
using namespace output;
 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
 
using namespace io;
 
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 30005;
const ld PI = 4*atan((ld)1);
 
struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator () (std::pair<T1, T2> const &pair) const
	{
		std::size_t h1 = std::hash<T1>()(pair.first);
		std::size_t h2 = std::hash<T2>()(pair.second);
 
		return h1 ^ h2;
	}
};

map<pi, vector<pii>> adj; vector<pi> low, high; unordered_set<int> vals; unordered_set<pi, pair_hash> vis; unordered_set<pi,ll, pair_hash> dist;
 
int main() {
   setIO(); 
   int N,M; re(N,M);   
   const int LIM = ceil(sqrt((double)N));
   pi fst = {-1,-1}; pi sec = {-1,-1};
   fax(i,M){
      int b,p; re(b,p);  
      if(fst.f == -1){
         fst = mp(b,p);
      } 
      else if(sec.f == -1){
         sec = mp(b,p);
      }
      if(p <= LIM){
         low.pb(mp(b,p));
         vals.insert(p);
      }
      else{
         high.pb(mp(b,p));
      }
   }
   trav(curr, low){
      adj[mp(curr.f, -1)].pb(mp(0,mp(curr.f, curr.s)));
      //dbg(mp(curr.f, -1), mp(0,mp(curr.f,curr.s)));
   }
   trav(curr, high){
      for(int j = 1; curr.f + (curr.s*j) < N; j++){
          adj[mp(curr.f,-1)].pb(mp(j,mp(curr.f+(curr.s*j),-1)));
          //dbg(mp(i,curr.s),mp(j,mp(i+(curr.s*j),-1)));
       }
       for(int j = 1; curr.f - (curr.s*j) >= 0; j++){
          adj[mp(curr.f,-1)].pb(mp(j,mp(curr.f-(curr.s*j),-1)));
          //dbg(mp(i,curr.s),mp(j,mp(i-(curr.s*j),-1)));
       }
   }
   fax(i,N){
     dist[mp(i,-1)] = INF;
     trav(curr, vals){
      adj[mp(i,curr)].pb(mp(0,mp(i,-1)));  
      dist[mp(i,curr)] = INF;
      if(i-curr >= 0){
         adj[mp(i, curr)].pb(mp(1,mp(i-curr,curr)));
      }
      if(i + curr < N){
         adj[mp(i,curr)].pb(mp(1,mp(i+curr,curr)));
      }
     }
   }
   priority_queue<pair<ll,pi>> pq;
   pq.push(mp(0,mp(fst.f, -1)));
   dist[mp(fst.f, -1)] = 0;
   while(!pq.empty()){
      pair<ll,pi> fr = pq.top(); pq.pop();
      if(vis.count(fr.s)){
         continue;
      }
      for(pii to : adj[fr.s]){
         if(vis.count(to.s)){
            continue;
         }
         if(dist[to.s] > dist[fr.s] + to.f){
            dist[to.s] = dist[fr.s] + to.f;
            pq.push(mp(-dist[to.s], to.s));
         }
      }
      vis.insert(fr.s);
   }
   ll d = dist[mp(sec.f, -1)];
   if(d != INF){
      pr(d, "\n");
      return 0;
   }
   pr(-1, "\n");
}
 

Compilation message

In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from skyscraper.cpp:3:
/usr/include/c++/7/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int>':
/usr/include/c++/7/type_traits:143:12:   required from 'struct std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> >'
/usr/include/c++/7/type_traits:154:31:   required from 'struct std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
/usr/include/c++/7/bits/unordered_set.h:98:63:   required from 'class std::unordered_set<std::pair<int, int>, long long int, pair_hash>'
skyscraper.cpp:141:140:   required from here
/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: expression cannot be used as a function
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from skyscraper.cpp:3:
/usr/include/c++/7/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >':
/usr/include/c++/7/bits/unordered_set.h:98:63:   required from 'class std::unordered_set<std::pair<int, int>, long long int, pair_hash>'
skyscraper.cpp:141:140:   required from here
/usr/include/c++/7/type_traits:154:31: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> >'
     : public __bool_constant<!bool(_Pp::value)>
                               ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/unordered_set:48:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:118,
                 from skyscraper.cpp:3:
/usr/include/c++/7/bits/unordered_set.h: In instantiation of 'class std::unordered_set<std::pair<int, int>, long long int, pair_hash>':
skyscraper.cpp:141:140:   required from here
/usr/include/c++/7/bits/unordered_set.h:98:63: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
                                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:105:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::key_type key_type;
                                             ^~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:106:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::value_type value_type;
                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:107:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::hasher hasher;
                                           ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:108:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::key_equal key_equal;
                                              ^~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:109:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:114:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::pointer  pointer;
                                             ^~~~~~~
/usr/include/c++/7/bits/unordered_set.h:115:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:116:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::reference  reference;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:117:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:118:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::iterator  iterator;
                                              ^~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:119:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:120:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:121:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:122:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::size_type  size_type;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:123:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:282:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       operator=(initializer_list<value_type> __l)
       ^~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:375:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
  emplace(_Args&&... __args)
  ^~~~~~~
/usr/include/c++/7/bits/unordered_set.h:419:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:423:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:478:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:679:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       equal_range(const key_type& __x)
       ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:683:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<long long int>, std::__detail::__is_noexcept_hash<std::pair<int, int>, long long int> > >'
       equal_range(const key_type& __x) const
       ^~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:179:10: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
      dist[mp(i,-1)] = INF;
          ^
skyscraper.cpp:182:11: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
       dist[mp(i,curr)] = INF;
           ^
skyscraper.cpp:193:8: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
    dist[mp(fst.f, -1)] = 0;
        ^
skyscraper.cpp:203:17: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
          if(dist[to.s] > dist[fr.s] + to.f){
                 ^
skyscraper.cpp:203:30: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
          if(dist[to.s] > dist[fr.s] + to.f){
                              ^
skyscraper.cpp:204:17: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
             dist[to.s] = dist[fr.s] + to.f;
                 ^
skyscraper.cpp:204:30: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
             dist[to.s] = dist[fr.s] + to.f;
                              ^
skyscraper.cpp:205:29: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
             pq.push(mp(-dist[to.s], to.s));
                             ^
skyscraper.cpp:210:15: error: no match for 'operator[]' (operand types are 'std::unordered_set<std::pair<int, int>, long long int, pair_hash>' and 'std::pair<int, int>')
    ll d = dist[mp(sec.f, -1)];
               ^
skyscraper.cpp: In function 'void io::setIn(std::__cxx11::string)':
skyscraper.cpp:112:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'void io::setOut(std::__cxx11::string)':
skyscraper.cpp:113:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~