oj.uz

Submission #1105712

# Submission time Handle Problem Language Result Execution time Memory
1105712 2024-10-27T11:56:40 Z errorgorn Cutting a Rectangle (BOI24_rectangle) C++17
100 / 100
 1090 ms 242364 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
ii arr[100005];

bool has[100005];
vector<int> B[5000005];
vector<int> S[5000005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	
	int sum=0;
	rep(x,1,n+1) sum+=arr[x].fi*arr[x].se;
	
	vector<int> ans;
	rep(l,1,5000005) if (sum%l==0 && l<=sum/l){
		int a=l,b=sum/l;
		
		rep(x,1,n+1){
			has[x]=false;
			B[arr[x].fi].clear();
			S[arr[x].se].clear();
		}
		
		rep(x,1,n+1){
			B[arr[x].fi].pub(x);
			S[arr[x].se].pub(x);
		}
		
		while (true){
			if (a<b) swap(a,b);
			
			bool h=false;
			
			if (a<5000005) for (auto it:B[a]) if (!has[it]){
				has[it]=h=true;
				b-=arr[it].se;
			}
			
			if (h) continue;
			
			for (auto it:S[b]) if (!has[it]){
				has[it]=h=true;
				a-=arr[it].fi;
			}
			
			if (h) continue;
			
			for (auto it:B[b]) if (!has[it]){
				has[it]=h=true;
				a-=arr[it].se;
			}
			
			if (!h) break;
		}
		
		if (a*b==0) ans.pub(l);
	}
	
	cout<<sz(ans)<<endl;
	for (auto it:ans) cout<<it<<endl;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 236360 KB Output is correct
2 Correct 70 ms 236608 KB Output is correct
3 Correct 73 ms 236360 KB Output is correct
4 Correct 76 ms 236624 KB Output is correct
5 Correct 77 ms 236452 KB Output is correct
6 Correct 72 ms 236616 KB Output is correct
7 Correct 73 ms 236616 KB Output is correct
8 Correct 74 ms 236592 KB Output is correct
9 Correct 70 ms 236360 KB Output is correct
10 Correct 82 ms 236624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 236620 KB Output is correct
2 Correct 89 ms 236616 KB Output is correct
3 Correct 130 ms 241556 KB Output is correct
4 Correct 159 ms 241596 KB Output is correct
5 Correct 91 ms 236360 KB Output is correct
6 Correct 240 ms 241396 KB Output is correct
7 Correct 190 ms 241588 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 236360 KB Output is correct
2 Correct 70 ms 236608 KB Output is correct
3 Correct 73 ms 236360 KB Output is correct
4 Correct 76 ms 236624 KB Output is correct
5 Correct 77 ms 236452 KB Output is correct
6 Correct 72 ms 236616 KB Output is correct
7 Correct 73 ms 236616 KB Output is correct
8 Correct 74 ms 236592 KB Output is correct
9 Correct 70 ms 236360 KB Output is correct
10 Correct 82 ms 236624 KB Output is correct
11 Correct 95 ms 236620 KB Output is correct
12 Correct 89 ms 236616 KB Output is correct
13 Correct 130 ms 241556 KB Output is correct
14 Correct 159 ms 241596 KB Output is correct
15 Correct 91 ms 236360 KB Output is correct
16 Correct 240 ms 241396 KB Output is correct
17 Correct 190 ms 241588 KB Output is correct
18 Correct 1090 ms 241680 KB Output is correct
19 Correct 123 ms 241684 KB Output is correct
20 Correct 386 ms 241664 KB Output is correct
21 Correct 426 ms 237472 KB Output is correct
22 Correct 222 ms 241596 KB Output is correct
23 Correct 188 ms 242356 KB Output is correct
24 Correct 78 ms 236616 KB Output is correct
25 Correct 388 ms 242364 KB Output is correct