제출 #377646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377646		Aldas25	Cutting a rectangle (LMIO18_staciakampis)	C++14	25 / 100	1097 ms	21484 KiB

staciakampis

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 500100, MAXK = 23;
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ld PI = asin(1) * 2;

void setIO () {
    FAST_IO;
}

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

int n;
ll a[MAXN], b[MAXN];
set<ll> ans;
ll sum = 0;
map<ll, set<ll>> byA, byB;
set<ll> checked;

void check (ll x) {
   // cout << "  1 checking x = " << x << endl;
    if (sum%x != 0) return;
   // cout << "  2 checking x = " << x << endl;
   // if (x*x > sum) return;
   // cout << "  3 checking x = " << x << endl;

    ll w = x, h = sum/x;

    if (w < h) swap(w,h);
    ll initH = h;

    if (checked.count(h)) return;
    checked.insert(h);

   // cout << "  checking h = " << h << endl;

    byA.clear();
    byB.clear();
    FOR(i, 1, n) {
        byA[a[i]].insert(b[i]);
        byB[b[i]].insert(a[i]);
    }

    while (w > 0 && h > 0) {
        if ((int)byA[w].size() > 0) {
            for (ll k : byA[w]) {
                h -= k;
                byB[k].erase(w);
            }
            byA[w].clear();
        } else if ((int)byB[h].size() > 0) {
            for (ll k : byB[h]) {
                w -= k;
                byA[k].erase(h);
            }
            byB[h].clear();
        } else if ((int)byA[h].size() > 0) {
            for (ll k : byA[h]) {
                w -= k;
                byB[k].erase(h);
            }
            byA[h].clear();
        } else {
            return;
        }

        if (w < h) swap(w, h);
    }

    ans.insert(initH);
}

int main() {
	setIO();

    cin >> n;
    FOR(i, 1, n) cin >> a[i] >> b[i];

    FOR(i ,1, n) sum += a[i]*b[i];

    FOR(i, 1, n) {
        check(a[i]);
        check(b[i]);
    }

    cout << (int)ans.size() << "\n";
    for (ll x : ans) cout << x << "\n";

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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