oj.uz

답안 #974753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974753 2024-05-03T18:12:47 Z AdamGS Cutting a rectangle (LMIO18_staciakampis) C++17
100 / 100
 217 ms 30308 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
set<pair<ll,ll>>A, B;
vector<ll>ans;
map<ll,ll>mp;
ll sum;
bool solve(ll x, ll y) {
  if(x<y) swap(x, y);
  if(y==0) return true;
  auto it=B.end(); --it;
  auto p=*it;
  it=A.end(); --it;
  auto q=*it;
  if(p.st>y || q.st>x) return false;
  if(p.st==y) {
    B.erase(p);
    A.erase({p.nd, p.st});
    bool xd=solve(x-p.nd, y);
    B.insert(p);
    A.insert({p.nd, p.st});
    return xd;
  }
  if(q.st==x) {
    A.erase(q);
    B.erase({q.nd, q.st});
    bool xd=solve(x, y-q.nd);
    A.insert(q);
    B.insert({q.nd, q.st});
    return xd;
  }
  it=A.lower_bound({y, -1});
  if(it==A.end()) return false;
  auto r=*it;
  if(r.st!=y) return false;
  A.erase(r);
  B.erase({r.nd, r.st});
  bool xd=solve(x-r.nd, y);
  A.insert(r);
  B.insert({r.nd, r.st});
  return xd;
}
void check(ll x) {
  if(sum%x!=0) return;
  x=min(x, sum/x);
  if(mp.find(x)!=mp.end()) return;
  mp[x]=1;
  if(solve(x, sum/x)) ans.pb(x);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll k;
  cin >> k;
  vector<pair<ll,ll>>T(k);
  rep(i, k) {
    cin >> T[i].nd >> T[i].st;
    sum+=T[i].st*T[i].nd;
    A.insert({T[i].nd, T[i].st});
    B.insert(T[i]);
  }
  sort(all(T));
  check(T[k-1].st);
  rep(i, k) if(T[i].nd>T[k-1].st) check(T[i].nd);
  if(ans.size()==0) {
    cout << 0 << '\n';
    return 0;
  }
  sort(all(ans));
  vector<ll>P;
  P.pb(ans[0]);
  for(auto i : ans) if(P.back()!=i) P.pb(i);
  cout << P.size() << '\n';
  for(auto i : P) cout << i << '\n';
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 173 ms 29200 KB Output is correct
5 Correct 154 ms 29352 KB Output is correct
6 Correct 162 ms 28792 KB Output is correct
7 Correct 185 ms 28704 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 173 ms 29200 KB Output is correct
12 Correct 154 ms 29352 KB Output is correct
13 Correct 162 ms 28792 KB Output is correct
14 Correct 185 ms 28704 KB Output is correct
15 Correct 126 ms 29524 KB Output is correct
16 Correct 168 ms 29408 KB Output is correct
17 Correct 217 ms 29264 KB Output is correct
18 Correct 41 ms 6232 KB Output is correct
19 Correct 178 ms 29356 KB Output is correct
20 Correct 183 ms 29636 KB Output is correct
21 Correct 3 ms 1368 KB Output is correct
22 Correct 120 ms 30308 KB Output is correct