oj.uz

Submission #377646

# Submission time Handle Problem Language Result Execution time Memory
377646 2021-03-14T14:58:45 Z Aldas25 Cutting a rectangle (LMIO18_staciakampis) C++14
25 / 100
 1000 ms 21484 KB 
#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;
}

Compilation message

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 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 384 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Execution timed out 1097 ms 21484 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 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 384 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Execution timed out 1097 ms 21484 KB Time limit exceeded
12 Halted 0 ms 0 KB -