Submission #1111588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111588		salmon	Cutting a Rectangle (BOI24_rectangle)	C++14	0 / 100	1 ms	592 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int N;
int u,v;
vector<pair<int,int>> lst;
bool bidone[100100];
long long int sum = 0;
long long int big = 0;
long long int small = 0;
set<pair<int,int>,greater<pair<int,int>>> sat;
set<pair<int,int>,greater<pair<int,int>>> sat1;
vector<int> ans;

int main(){

    scanf(" %d",&N);

    for(int i = 0; i < N; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);

        sum += u * (long long int ) v;

        lst.push_back({u,v});

        big = max(big,0LL + u);
        small = max(small,0LL + v);

        sat.insert({u,v});
        sat1.insert({v,u});
    }

    long long int h = min(small,sum/small);
    long long int h1 = max(small,sum/small);

    while(sat.size() > 1){
        if(h == sat1.begin() -> first){
            h1 -= sat1.begin() -> second;
            sat.erase({sat1.begin() -> second, sat1.begin() -> first});
            sat1.erase(sat1.begin());
        }
        else if(h1 == sat.begin() -> first){
            h -= sat.begin() -> second;
            sat1.erase({sat.begin() -> second, sat.begin() -> first});
            sat.erase(sat.begin());
        }
        else{
            break;
        }

        long long int temp = h;
        h = min(h,h1);
        h1 = max(temp,h1);
    }

    if((int)sat.size() == 1 && (pair<long long int, long long int>)(*sat.begin()) == make_pair(h1,h) ){
        ans.push_back(min(small,sum/small));
    }


    for(int i = 0; i < N; i++){
        for(int i = 0; i < N; i++){
            sat.insert(lst[i]);
            sat1.insert({lst[i].second,lst[i].first});
        }

        small = lst[i].first;
        long long int h = min(small,sum/small);
        long long int h1 = max(small,sum/small);

        while(sat.size() > 1){
            if(h == sat1.begin() -> first){
                h1 -= sat1.begin() -> second;
                sat.erase({sat1.begin() -> second, sat1.begin() -> first});
                sat1.erase(sat1.begin());
            }
            else if(h1 == sat.begin() -> first){
                h -= sat.begin() -> second;
                sat1.erase({sat.begin() -> second, sat.begin() -> first});
                sat.erase(sat.begin());
            }
            else{
                break;
            }

            long long int temp = h;
            h = min(h,h1);
            h1 = max(temp,h1);
        }


        if((int)sat.size() == 1 && (pair<long long int, long long int>)(*sat.begin()) == make_pair(h1,h) ){
            ans.push_back(min(small,sum/small));
        }
    }

    sort(ans.begin(),ans.end());
    ans.resize(unique(ans.begin(), ans.end()) - ans.begin());

    printf("%d\n",ans.size());

    for(int i : ans) printf("%d\n",i);



}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  101 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %ld
Main.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
Main.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 55