oj.uz

Submission #538253

# Submission time Handle Problem Language Result Execution time Memory
538253 2022-03-16T12:33:59 Z idas Cutting a rectangle (LMIO18_staciakampis) C++11
100 / 100
 887 ms 159808 KB 
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define all(x) (x).begin(), (x).end()
#define le(vec) vec[vec.size()-1]
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e13;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

#define int long long

const int N=1e5+10;
int n, a[N], b[N];
vector<pii> inf;
ll area;

bool can(int x, int y)
{
    if(x*y!=area) return false;

    map<int, stack<pii>> ar, br;
    FOR(i, 0, n)
    {
        ar[inf[i].f].push({inf[i].s, i});
        br[inf[i].s].push({inf[i].f, i});
    }

    map<int, bool> v;
    while(x>0 && y>0){
        while(!ar[x].empty() && v[ar[x].top().s]) ar[x].pop();
        while(!br[x].empty() && v[br[x].top().s]) br[x].pop();
        while(!ar[y].empty() && v[ar[y].top().s]) ar[y].pop();
        while(!br[y].empty() && v[br[y].top().s]) br[y].pop();

        if(x<y) swap(x, y);

        if(sz(ar[x])){
            pii tp=ar[x].top();
            v[tp.s]=true;
            y-=tp.f;
            ar[x].pop();
            continue;
        }

        if(sz(br[y])){
            pii tp=br[y].top();
            v[tp.s]=true;
            x-=tp.f;
            br[y].pop();
            continue;
        }

        if(sz(ar[y])){
            pii tp=ar[y].top();
            v[tp.s]=true;
            x-=tp.f;
            ar[y].pop();
            continue;
        }
        return false;
    }
    return true;
}

signed main()
{
    setIO();
    cin >> n;
    set<int> aa, bb;
    FOR(i, 0, n)
    {
        cin >> a[i] >> b[i];
        inf.pb({a[i],b[i]});
        area+=a[i]*b[i];
        aa.insert(a[i]);
        bb.insert(b[i]);
    }

    sort(all(inf), greater<pii>());
    FOR(i, 0, n)
    {
        a[i]=inf[i].f; b[i]=inf[i].s;
    }

    set<int> ans;

//    for(ll i=1; i*i<=area; i++){
//        if(area%i==0){
//            ll x=i, y=area/x;
//            if(can(x, y)){
//                ans.insert(x);
//            }
//        }
//    }

    if(area%a[0]==0){
        if(aa.count(area/a[0]-b[0])){
            int x=a[0], y=area/a[0];
            if(can(x, y)){
                ans.insert(min(x, y));
            }
        }

        if(bb.count(area/a[0]-b[0])){
            int x=a[0], y=area/a[0];
            if(can(x, y)){
                ans.insert(min(x, y));
            }
        }
    }

    if(area%b[0]==0){
        if(aa.count(area/b[0]-a[0])){
            int x=b[0], y=area/b[0];
            if(can(x, y)){
                ans.insert(min(x, y));
            }
        }

        if(bb.count(area/b[0]-a[0])){
            int x=b[0], y=area/b[0];
            if(can(x, y)){
                ans.insert(min(x, y));
            }
        }
    }

    FOR(i, 1, n)
    {
        if(area%(a[0]+b[i])==0 && area/(a[0]+b[i])==a[i]){
            int x=a[0]+b[i], y=a[i];
            if(can(x, y)){
                ans.insert(min(x, y));
            }
        }

        if(area%(a[0]+a[i])==0 && area/(a[0]+a[i])==b[i]){
            int x=a[0]+a[i], y=b[i];
            if(can(x, y)){
                ans.insert(min(x, y));
            }
        }
    }

    ll now=b[0];
    bool bad=false;
    FOR(i, 1, n)
    {
        if(a[i]!=now && b[i]!=now){
            bad=true;
            break;
        }
    }

    if(!bad){
        ans.insert(now);
    }

    cout << sz(ans) << '\n';
    for(auto x : ans){
        cout << x << '\n';
    }
}

Compilation message

staciakampis.cpp: In function 'void setIO(std::string)':
staciakampis.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
staciakampis.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 303 ms 158456 KB Output is correct
5 Correct 302 ms 158416 KB Output is correct
6 Correct 302 ms 155284 KB Output is correct
7 Correct 293 ms 155324 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 303 ms 158456 KB Output is correct
12 Correct 302 ms 158416 KB Output is correct
13 Correct 302 ms 155284 KB Output is correct
14 Correct 293 ms 155324 KB Output is correct
15 Correct 271 ms 159488 KB Output is correct
16 Correct 741 ms 159508 KB Output is correct
17 Correct 887 ms 159408 KB Output is correct
18 Correct 317 ms 32076 KB Output is correct
19 Correct 752 ms 159436 KB Output is correct
20 Correct 258 ms 159808 KB Output is correct
21 Correct 11 ms 7508 KB Output is correct
22 Correct 54 ms 8976 KB Output is correct