제출 #652258

#제출 시각아이디문제언어결과실행 시간메모리
652258pauloamedJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1094 ms154724 KiB
#include<bits/stdc++.h> using namespace std; #define int long long struct Node{ int i, x; // se i == -1, eh col int cost; bool operator<(const Node &n) const{ return cost > n.cost; } }; namespace smallpq{ const int MAXV = 1e5; queue<Node> q[MAXV]; int tot_in[MAXV]; int tot_out[MAXV]; class QComp{ public: bool operator()(int a, int b){ return q[a].front() < q[b].front(); } }; int _size = 0; priority_queue<int, vector<int>, QComp> pq; int size() { return _size; } void push(Node x, int w) { q[w].push(move(x)); if(++tot_in[w] - tot_out[w] == 1) pq.push(w); _size++; } Node top() { return q[pq.top()].front(); } void pop() { auto w = pq.top(); pq.pop(); q[w].pop(); if(q[w].size()) pq.push(w); tot_out[w]++; _size--; } }; #include<bits/stdc++.h> using namespace std; const int MAXN = 30010; vector<int> col2i[MAXN]; vector<int> ans[MAXN]; int ps[MAXN]; int x2j(int id, int x){ int p = ps[id]; return x / p; } int& ans_at(int i, int x){ if(i == -1) return ans[i + 1][x]; else return ans[i + 1][x2j(i, x)]; } map<pair<int,int>, vector<int>> pb2bs; int32_t main(){ cin.tie(NULL)->sync_with_stdio(false); int n, m; cin >> n >> m; int B[2], P[2]; cin >> B[0] >> P[0]; cin >> B[1] >> P[1]; for(int i = 2; i < m; ++i){ int b, p; cin >> b >> p; pb2bs[make_pair(p, b % p)].push_back(b); } ans[0] = vector<int>(n, INT_MAX); int id = 0; for(auto [pb, bs] : pb2bs){ auto [p, b] = pb; ps[id] = p; for(int j = b; j < n; j += p){ ans[id+1].push_back(INT_MAX); } for(auto bb : bs){ col2i[bb].push_back(id); } id++; } for(int i = (B[0] % P[0]); i < n; i += P[0]){ int dist = abs(i - B[0]) / P[0]; smallpq::push({-1, i, ans_at(-1, i) = dist}, dist); } // print(); while(smallpq::size() > 0){ auto maybe_update = [&](int p, int x, int val, int d){ if(ans_at(p, x) > val){ Node X = {p, x, ans_at(p, x) = val}; smallpq::push(X, d); } }; auto [i, x, cost] = smallpq::top(); smallpq::pop(); if(cost > ans_at(i, x)) continue; // cout << i << " " << x << " " << cost << "\n"; if(i == -1){ for(auto i : col2i[x]){ maybe_update(i, x, cost, 0); } }else{ // sou power i na coluna x maybe_update(-1, x, cost, 0); if(x + ps[i] < n){ maybe_update(i, x + ps[i], cost + 1, 1); } if(x - ps[i] >= 0){ maybe_update(i, x - ps[i], cost + 1, 1); } } // print(); } cout << ((ans_at(-1, B[1]) == INT_MAX)? -1 : ans_at(-1, B[1])) << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:91:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |   for(auto [pb, bs] : pb2bs){
      |            ^
skyscraper.cpp:92:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     auto [p, b] = pb;
      |          ^
skyscraper.cpp:123:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |     auto [i, x, cost] = smallpq::top();
      |          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...