Submission #1257516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257516		G_thang_dizz_lenhi	Cutting a Rectangle (BOI24_rectangle)	C++17	0 / 100	0 ms	324 KiB

Main

#include<bits/stdc++.h>
typedef int ii;
typedef long long ll;

using namespace std;

const string name = "";
const ii MOD = 1e9 + 7;
const ii N = 1e5 + 10;

pair<ii,ii> rec[N];
ii n;
ll s = 0;

void INP(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen((name + ".inp").c_str(),"r")){
        freopen((name + ".inp").c_str(),"r",stdin);
        freopen((name + ".out").c_str(),"w",stdout);
    }
    cin >> n;
    for (ii i = 1;i <= n;i++){
        cin >> rec[i].first >> rec[i].second;
        s += rec[i].first * rec[i].second;
    }
}

map<pair<ii,ii>,bool> mp;

bool dp(ii pos,ll a,ll b){
    if (pos == 0) return true;
    if (mp.count(make_pair(a,b)) != 0) return mp[make_pair(a,b)];
    bool res = false;
    if (rec[pos].first == a){
        res = res | (dp(pos - 1,a,b - rec[pos].second));
        if (res){
            return mp[make_pair(a,b)] = res;
        }
    }
    if (rec[pos].second == a){
        res = res | (dp(pos - 1,a,b - rec[pos].first));
        if (res){
            return mp[make_pair(a,b)] = res;
        }
    }
    if (rec[pos].first == b){
        res = res | (dp(pos - 1,a - rec[pos].second,b));
        if (res){
            return mp[make_pair(a,b)] = res;
        }
    }
    if (rec[pos].second == b){
        res = res | (dp(pos - 1,a - rec[pos].first,b));
        if (res){
            return mp[make_pair(a,b)] = res;
        }
    }
    return false;
}

int main(){
    INP();
    vector<ii> res;
    cerr << s << endl;
    ll a = rec[n].first;
    ll b = (s - rec[n].first * rec[n].second) / rec[n].first;
    if (dp(n - 1,a,b)) res.push_back(b);
    cerr << a << " " << b << endl;
    if (rec[n].second != rec[n].first){
    a = rec[n].second;
    b = (s - rec[n].first * rec[n].second) / rec[n].second;
    if (dp(n - 1,a,b)) res.push_back(b);
    cerr << a << " " << b << endl;
    }
    cout << res.size() << endl;
    for (ii x : res) cout << x << endl;
    return 0;
}

//NGT 1600-2000 cf
//1/200 hard quests

Compilation message (stderr)

Main.cpp: In function 'void INP()':
Main.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((name + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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