結果
問題 | No.112 ややこしい鶴亀算 |
ユーザー | Tatsu_mr |
提出日時 | 2024-10-28 23:38:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 3,450 bytes |
コンパイル時間 | 3,978 ms |
コンパイル使用メモリ | 266,328 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-28 23:38:15 |
合計ジャッジ時間 | 4,857 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>#define For(i, a, b) for(long long i = a; i < b; i++)#define rep(i, n) For(i, 0, n)#define rFor(i, a, b) for(long long i = a; i >= b; i--)#define ALL(v) (v).begin(), (v).end()#define rALL(v) (v).rbegin(), (v).rend()using namespace std;using lint = long long;using ld = long double;int INF = 2000000000;lint LINF = 1000000000000000000;template <class T>struct Edge {int from, to;T cost;int idx;Edge() {}Edge(int to_) : to(to_) {}Edge(int to_, T cost_) : to(to_), cost(cost_) {}Edge(int from_, int to_, int idx_) : from(from_), to(to_), idx(idx_) {}Edge(int from_, int to_, T cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {}};template <class T> using Graph = vector<vector<Edge<T>>>;using graph = Graph<long long>;using edge = Edge<long long>;#define add emplace_backstruct Dijkstra {private:graph g;int n, s;vector<long long> d;vector<edge> prev;vector<bool> visit;priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;public:Dijkstra(graph g_, int s_) : g(g_), n(g.size()), s(s_), d(n, 1000000000000000000), prev(n), visit(n, false) {d[s] = 0LL;pq.emplace(d[s], s);while (!pq.empty()) {int v = pq.top().second;pq.pop();if (visit[v]) {continue;}visit[v] = true;for (auto e : g[v]) {int nv = e.to;long long nc = e.cost;if (d[nv] > d[v] + nc) {d[nv] = d[v] + nc;prev[nv] = e;pq.emplace(d[nv], nv);}}}}vector<long long> dists() {return d;}long long dist(int t) {return d[t];}vector<edge> route(int t) {if (s == t || d[t] == 1000000000000000000) {return {};}vector<edge> res;int cur = t;while (cur != s) {res.emplace_back(prev[cur]);cur = prev[cur].from;}reverse(res.begin(), res.end());return res;}};int main() {int n;cin >> n;vector<int> a(n);rep(i, n) {cin >> a[i];}// t[i]/k[i] : i 匹目を除くと鶴は t[i] 匹、亀は k[i] 匹vector<int> t(n), k(n);rep(i, n) {k[i] = (a[i] - 2 * (n - 1)) / 2;t[i] = n - 1 - k[i];}graph g(n);rep(i, n) {rep(j, n) {if (i == j) {continue;}if (t[i] == t[j]) {g[i].add(j, 2);g[j].add(i, 2);} else {g[i].add(j, 1);g[j].add(i, 1);}}}auto d = Dijkstra(g, 0).dists();int x = 0, y = 0;rep(i, n) {d[i] %= 2;if (d[i] == 0) {x++;} else {y++;}}rep(i, n) {if (d[i] == 0) {if (2 * (x - 1) + 4 * y != a[i]) {cout << y << " " << x << endl;return 0;}} else {if (2 * x + 4 * (y - 1) != a[i]) {cout << y << " " << x << endl;return 0;}}}cout << x << " " << y << endl;}