oj.uz

Submission #977811

# Submission time Handle Problem Language Result Execution time Memory
977811 2024-05-08T11:18:50 Z new_acc Cutting a rectangle (LMIO18_staciakampis) C++14
100 / 100
 134 ms 14644 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int n;
pair<ll,ll> t[N];
set<pair<int,int>> s1,s2;
bool check(ll x,ll y){
    bool res=1;
    vector<pair<int,int>> usu;
    for(int i=1;i<=n;i++){
        if(x>y) swap(x,y);
        auto it=s2.end(),it2=s1.end();
        it--,it2--;
        if((it->fi)>x or (it2->fi)>y) break;
        pair<int,int> curr=*it,curr2=*it2;
        if(curr.fi==x){
            y-=curr.se;
            usu.push_back({curr.se,curr.fi});
            s2.erase(it);
            s1.erase({curr.se,curr.fi});
            continue;
        }
        if(curr2.fi==y){
            x-=curr2.se;
            usu.push_back(curr2);
            s1.erase(it2);
            s2.erase({curr2.se,curr2.fi});
            continue;
        }
        auto it3=s1.lower_bound({x,0});
        if(it3!=s1.end() and (it3->fi)==x){
            pair<int,int> curr3=*it3;
            y-=curr3.se;
            usu.push_back(curr3);
            s1.erase(it3);
            s2.erase({curr3.se,curr3.fi});

        }else break;
    }
    for(auto u:usu) s1.insert(u),s2.insert({u.se,u.fi});
    return usu.size()==n;
}
void solve(){
    cin>>n;
    ll r=0;
    for(int i=1;i<=n;i++){
        cin>>t[i].fi>>t[i].se;
        r+=(ll)t[i].fi*(ll)t[i].se;
        s1.insert(t[i]),s2.insert({t[i].se,t[i].fi});
    }
    sort(t+1,t+1+n,[&](auto a,auto b){return a.se<b.se;});
    vector<pair<ll,ll>> cr;
    for(int i=1;i<=n;i++){
        if(!(r%t[i].fi)) 
            cr.push_back({min(t[i].fi,r/t[i].fi),max(t[i].fi,r/t[i].fi)});
    }
    if(!(r%t[n].se))
        cr.push_back({min(t[n].se,r/t[n].se),max(t[n].se,r/t[n].se)});
    vl ans;
    sort(cr.begin(),cr.end());
    for(int i=0;i<cr.size();i++){
        if((!i or cr[i]!=cr[i-1]) and check(cr[i].fi,cr[i].se))
            ans.push_back(cr[i].fi);
    }
    cout<<ans.size()<<"\n";
    for(auto u:ans) cout<<u<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message

staciakampis.cpp: In function 'bool check(ll, ll)':
staciakampis.cpp:57:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     return usu.size()==n;
      |            ~~~~~~~~~~^~~
staciakampis.cpp:24:10: warning: unused variable 'res' [-Wunused-variable]
   24 |     bool res=1;
      |          ^~~
staciakampis.cpp: In function 'void solve()':
staciakampis.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<cr.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory 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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 114 ms 13864 KB Output is correct
5 Correct 104 ms 13904 KB Output is correct
6 Correct 105 ms 13768 KB Output is correct
7 Correct 101 ms 13652 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory 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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 114 ms 13864 KB Output is correct
12 Correct 104 ms 13904 KB Output is correct
13 Correct 105 ms 13768 KB Output is correct
14 Correct 101 ms 13652 KB Output is correct
15 Correct 74 ms 13836 KB Output is correct
16 Correct 115 ms 13904 KB Output is correct
17 Correct 134 ms 13964 KB Output is correct
18 Correct 35 ms 4944 KB Output is correct
19 Correct 110 ms 13736 KB Output is correct
20 Correct 114 ms 13932 KB Output is correct
21 Correct 3 ms 1112 KB Output is correct
22 Correct 74 ms 14644 KB Output is correct