# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244026 | 2020-07-02T13:27:21 Z | patrikpavic2 | Cutting a rectangle (LMIO18_staciakampis) | C++17 | 13 ms | 12032 KB |
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> #include <set> #define X first #define Y second #define PB push_back using namespace std; typedef pair < int, int > pii; typedef pair < pii, bool > st; typedef long long ll; const int N = 1e5 + 500; const int M = 5e5 + 500; vector < int > ima[M]; set < pii > svi; queue < st > Q; int A[N], B[N], n; ll P = 0; int main(){ scanf("%d", &n); for(int i = 0;i < n;i++){ scanf("%d%d", A + i, B + i); if(i){ ima[A[i]].PB(B[i]); ima[B[i]].PB(A[i]); } P += (ll)A[i] * B[i]; } Q.push({{A[0], B[0]}, 0}); Q.push({{A[0], B[0]}, 1}); for(int i = 0;i < M;i++) sort(ima[i].begin(), ima[i].end()); for(;!Q.empty();Q.pop()){ st cur = Q.front(); if((ll)cur.X.X * cur.X.Y == P){ svi.insert({cur.X.X, cur.X.Y}); continue; } //printf("%d %d %d\n", cur.X.X, cur.X.Y); if(!cur.Y){ if(cur.X.X < M){ ll dos = 0; for(int sad : ima[cur.X.X]){ dos += sad; Q.push({{cur.X.X, cur.X.Y + dos}, 1}); } } } if(cur.Y){ if(cur.X.Y < M){ ll dos = 0; for(int sad : ima[cur.X.Y]){ dos += sad; Q.push({{cur.X.X + dos, cur.X.Y}, 0}); } } } } printf("%d\n", (int)svi.size()); for(pii mog : svi) printf("%d\n", min(mog.X, mog.Y)); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12032 KB | Output is correct |
2 | Incorrect | 12 ms | 12032 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 12032 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12032 KB | Output is correct |
2 | Incorrect | 12 ms | 12032 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |