oj.uz

Submission #244031

# Submission time Handle Problem Language Result Execution time Memory
244031 2020-07-02T13:34:29 Z patrikpavic2 Cutting a rectangle (LMIO18_staciakampis) C++17
0 / 100
 24 ms 24320 KB 
#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 long long ll;
typedef pair < ll, ll > pll;
typedef pair < pll, bool > st;

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

vector < int > ima[M];
set < ll > 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(min(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(ll mog : svi)
		printf("%lld\n", mog);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12032 KB Output is correct
2 Correct 14 ms 12032 KB Output is correct
3 Runtime error 24 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12032 KB Output is correct
2 Correct 14 ms 12032 KB Output is correct
3 Runtime error 24 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -