#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define F first
#define S second
#define PB push_back
#define DEBUG(x) cerr << #x << " = " << x << "\n";
using ll = long long;
using pll = pair<ll, ll>;
int k;
ll TotalArea = 0;
set<ll> CheckedLengths;
set<ll> AvailableLengths;
map<ll, multiset<ll, greater<ll>>> AllByLength;
map<ll, multiset<ll, greater<ll>>> ByLength;
vector<pll> Rectangles;
bool test(ll w, ll h)
{
//auto t1 = high_resolution_clock::now();
CheckedLengths.insert(min(w,h));
//cerr << "TEST: " << w << " " << h << endl;
ByLength = AllByLength;
/*
auto t2 = high_resolution_clock::now();
auto duration = duration_cast<milliseconds>( t2 - t1 ).count();
cerr << "Copy ended: " << duration << "ms\n";
*/
/*
for(auto it = ByLength.begin(); it != ByLength.end(); it++)
{
cerr << it->first << ":\n\t";
for(int x : it->second)
{
cerr << x << " ";
}
cerr << endl;
}
*/
bool changed = true;
while(changed)
{
//DEBUG(w);
//DEBUG(h);
changed = false;
if(h > w)
{
swap(w, h);
}
if(ByLength.count(w))
{
changed = true;
multiset<ll> Erase;
for(ll x : ByLength[w])
{
Erase.insert(x);
h -= x;
}
auto pointerByLengthW = &ByLength[w];
for(ll x : Erase)
{
if(x != w)
{
ByLength[x].erase(ByLength[x].find(w));
pointerByLengthW->erase(pointerByLengthW->find(x));
}
else
{
ByLength[x].erase(ByLength[x].find(w));
}
if(!ByLength[x].size())
{
ByLength.erase(x);
}
}
ByLength[w].clear();
ByLength.erase(w);
}
else if(ByLength.count(h))
{
changed = true;
multiset<ll> Erase; // rikiuoti pagal ilgi, nes jei reikia trinti, tai trinti ilgiausia
for(ll x : ByLength[h])
{
Erase.insert(x);
w -= x;
if(ByLength.begin()->first <= w || w < h) /// Patikrinti ar reikia nutraukti, kai w < h, ir gali buti per letai
{
break;
}
}
for(ll x : Erase)
{
if(x != h)
{
ByLength[h].erase(ByLength[h].find(x));
ByLength[x].erase(ByLength[x].find(h));
}
else
{
ByLength[h].erase(ByLength[h].find(x));
}
if(!ByLength[x].size())
{
ByLength.erase(x);
}
}
if(!ByLength[h].size()) // pirmas else if ciklas perejo visus elementus
{
ByLength.erase(h);
}
}
}
//cerr << "-----------------------\n";
/*
t2 = high_resolution_clock::now();
duration = duration_cast<milliseconds>( t2 - t1 ).count();
cout << "Test took: " << duration << "ms\n";
*/
return w == 0 || h == 0;
}
int main()
{
scanf("%d", &k);
Rectangles.resize(k);
for(int i = 0; i < k; i++)
{
scanf("%lld%lld", &Rectangles[i].F, &Rectangles[i].S);
TotalArea += Rectangles[i].F * Rectangles[i].S;
}
for(int i = 0; i < k; i++)
{
if(Rectangles[i].F != Rectangles[i].S)
{
AllByLength[Rectangles[i].F].insert(Rectangles[i].S);
AllByLength[Rectangles[i].S].insert(Rectangles[i].F);
}
else
{
AllByLength[Rectangles[i].F].insert(Rectangles[i].S);
}
}
for(int i = 0; i < k; i++)
{
ll a = Rectangles[i].F, b = Rectangles[i].S;
// test a x b;
if(TotalArea % b == 0 && !AvailableLengths.count(min(TotalArea / b, b)) && !CheckedLengths.count(min(TotalArea / b, b)))
{
if(test(TotalArea / b, b))
{
AvailableLengths.insert(min(TotalArea / b, b));
}
}
// test b x a;
if(TotalArea % a == 0 && !AvailableLengths.count(min(TotalArea / a, a)) && !CheckedLengths.count(min(TotalArea / a, a)))
{
if(test(TotalArea / a, a))
{
AvailableLengths.insert(min(TotalArea / a, a));
}
}
}
printf("%d\n", AvailableLengths.size());
for(ll x : AvailableLengths)
{
printf("%lld\n", x);
}
return 0;
}
/* INPUT
10
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
4
1 1
2 1
3 1
6 2
3
2 1
3 2
4 2
*/
Compilation message
staciakampis.cpp: In function 'int main()':
staciakampis.cpp:182:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wformat=]
182 | printf("%d\n", AvailableLengths.size());
| ~^ ~~~~~~~~~~~~~~~~~~~~~~~
| | |
| int std::set<long long int>::size_type {aka long unsigned int}
| %ld
staciakampis.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
staciakampis.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
144 | scanf("%lld%lld", &Rectangles[i].F, &Rectangles[i].S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Execution timed out |
1091 ms |
39568 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
0 ms |
364 KB |
Output is correct |
| 11 |
Execution timed out |
1091 ms |
39568 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
