Submission #244026

#	Time	Username	Problem	Language	Result	Execution time	Memory
244026		patrikpavic2	Cutting a rectangle (LMIO18_staciakampis)	C++17	0 / 100	13 ms	12032 KiB

staciakampis

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef pair < pii, bool > st;
typedef long long ll;

const int N = 1e5 + 500;
const int M = 5e5 + 500;

vector < int > ima[M];
set < pii > svi;
queue < st > Q;
int A[N], B[N], n;
ll P = 0;

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d%d", A + i, B + i);
		if(i){
			ima[A[i]].PB(B[i]);
			ima[B[i]].PB(A[i]);
		}
		P += (ll)A[i] * B[i];
	}
	Q.push({{A[0], B[0]}, 0});
	Q.push({{A[0], B[0]}, 1});
	for(int i = 0;i < M;i++)
		sort(ima[i].begin(), ima[i].end());
	for(;!Q.empty();Q.pop()){
		st cur = Q.front();
		if((ll)cur.X.X * cur.X.Y == P){
			svi.insert({cur.X.X, cur.X.Y});
			continue;
		}
		//printf("%d %d %d\n", cur.X.X, cur.X.Y);
		if(!cur.Y){
			if(cur.X.X < M){
				ll dos = 0;		
				for(int sad : ima[cur.X.X]){
					dos += sad;
					Q.push({{cur.X.X, cur.X.Y + dos}, 1});
				}
			}
		}
		if(cur.Y){
			if(cur.X.Y < M){
				ll dos = 0;		
				for(int sad : ima[cur.X.Y]){
					dos += sad;
					Q.push({{cur.X.X + dos, cur.X.Y}, 0});
				}
			}
		}
	}
	printf("%d\n", (int)svi.size());
	for(pii mog : svi)
		printf("%d\n", min(mog.X, mog.Y));
}

Compilation message (stderr)

staciakampis.cpp: In function 'int main()':
staciakampis.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
staciakampis.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", A + i, B + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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