oj.uz

Submission #430710

# Submission time Handle Problem Language Result Execution time Memory
430710 2021-06-17T01:55:10 Z Mohammed_Atalah New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 24700 KB 

/////home/mohammed/.config/sublime-text-3/Packages/User

/*input

*/
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <sstream>
#include <iterator>
#include <cstdlib>
#include <unordered_map>
#include <map>
#include <list>
#include <set>

using namespace std;
using bin = std::bitset<8>;

#define endl ("\n")
#define pi (3.141592653589)
#define mod 1000000007
#define int int64_t
#define float double
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
#define min3(a, b, c) min({a,b,c})
#define max3(a, b, c) max({a,b,c})
#define min4(a, b, c, d) min({a,b,c,d})
#define max4(a, b, c, d) max({a,b,c,d})
#define rrep(i, n) for(int i=n-1;i>=0;i--)
#define rep(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ld long double
#define scanArray(a,n) for(int i = 0; i < n; i++){cin >> a[i];}
#define coutArray(a,n) for(int i = 0; i < n; i++){cout << a[i] << " ";};cout << endl;
#define input(type, n) type n; cin>>n;



struct debugger
{
	template<typename T> debugger& operator , (const T& v)
	{
		cerr << v << " ";
		return *this;
	}
} dbg;

bool check_key(map<int, int> m, int key)
{
	if (m.find(key) == m.end())
		return false;

	return true;
}


vector<int> SieveOfEratosthenes(int n)
{
	bool prime[n + 1];
	memset(prime, true, sizeof(prime));


	vector<int> res;
	for (int p = 2; p * p <= n; p++)
	{
		if (prime[p] == true)
		{
			for (int i = p * p; i <= n; i += p)
				prime[i] = false;
		}
	}

	for (int p = 2; p <= n; p++)
		if (prime[p])
			res.push_back(p);
	//cout << p << " ";
	return res;
}

// function to convert decimal to binary
bin decToBinary(int n)
{
	// array to store binary number
	int binaryNum[32];

	// counter for binary array
	int i = 0;
	while (n > 0) {

		// storing remainder in binary array
		binaryNum[i] = n % 2;
		n = n / 2;
		i++;
	}
	string x = "";
	// printing binary array in reverse order
	for (int j = i - 1; j >= 0; j--) {
		x += to_string(binaryNum[j]);
	}
	bin result{x};
	return result;
}
// for example:
// bin result = decToBinary(2);
// bin result2 = decToBinary(10);
// bin z = result xor result2;
// cout << z;
// return 0;
int convertBinaryToDecimal(long long n)
{
	int decimalNumber = 0, i = 0, remainder;
	while (n != 0)
	{
		remainder = n % 10;
		n /= 10;
		decimalNumber += remainder * pow(2, i);
		++i;
	}
	return decimalNumber;
}
int factorial(int n) {

	long long res = 1;
	for (int i = 1; i <= n; i++) {
		res = ((res * i) % mod + mod) % mod ;
	}
	return res;
}





int32_t main()
{
	fast;


	input(int, streets); input(int, types); input(int, queries);
	vector<vector<int>> s;
	s.resize(streets);
	rep(i, streets) {
		input(int, num1); s[i].pb(num1);
		input(int, num2); s[i].pb(num2);
		input(int, num3); s[i].pb(num3);
		input(int, num4); s[i].pb(num4);
	}


	rep(_, queries) {

		input(int, location); input(int, year);
		int mx = 0;
		set<int> se;
		vector<int> nearest;
		nearest.resize(types + 1);

		for (auto vec : s) {
			if (vec[2] <= year && year <= vec[3]) {
				int sp = abs(location - vec[0]);
				if (nearest[vec[1]] == 0) {
					nearest[vec[1]] = sp + 1;
				} else if (nearest[vec[1]] > sp + 1) {
					nearest[vec[1]] = sp + 1;
				}
				se.insert(vec[1]);
			}
		}
		if (se.size() == types) {
			int res = 0;
			for (int i = 1; i < nearest.size(); i++) {
				if (nearest[i] - 1 > res) {
					res = nearest[i] - 1;
				}
			}
			cout << res << endl;
		} else {
			cout << -1 << endl;
		}

	}

}

Compilation message

new_home.cpp: In function 'int32_t main()':
new_home.cpp:181:17: warning: comparison of integer expressions of different signedness: 'std::set<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  181 |   if (se.size() == types) {
      |       ~~~~~~~~~~^~~~~~~~
new_home.cpp:183:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |    for (int i = 1; i < nearest.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
new_home.cpp:165:7: warning: unused variable 'mx' [-Wunused-variable]
  165 |   int mx = 0;
      |       ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 16 ms 332 KB Output is correct
8 Correct 14 ms 368 KB Output is correct
9 Correct 17 ms 332 KB Output is correct
10 Correct 8 ms 360 KB Output is correct
11 Correct 7 ms 324 KB Output is correct
12 Correct 9 ms 356 KB Output is correct
13 Correct 8 ms 360 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 13 ms 332 KB Output is correct
16 Correct 16 ms 372 KB Output is correct
17 Correct 8 ms 360 KB Output is correct
18 Correct 19 ms 368 KB Output is correct
19 Correct 15 ms 376 KB Output is correct
20 Correct 11 ms 320 KB Output is correct
21 Correct 26 ms 376 KB Output is correct
22 Correct 19 ms 384 KB Output is correct
23 Correct 18 ms 332 KB Output is correct
24 Correct 12 ms 332 KB Output is correct
25 Correct 8 ms 332 KB Output is correct
26 Correct 7 ms 332 KB Output is correct
27 Correct 8 ms 316 KB Output is correct
28 Correct 6 ms 332 KB Output is correct
29 Correct 7 ms 364 KB Output is correct
30 Correct 5 ms 332 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 16 ms 332 KB Output is correct
8 Correct 14 ms 368 KB Output is correct
9 Correct 17 ms 332 KB Output is correct
10 Correct 8 ms 360 KB Output is correct
11 Correct 7 ms 324 KB Output is correct
12 Correct 9 ms 356 KB Output is correct
13 Correct 8 ms 360 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 13 ms 332 KB Output is correct
16 Correct 16 ms 372 KB Output is correct
17 Correct 8 ms 360 KB Output is correct
18 Correct 19 ms 368 KB Output is correct
19 Correct 15 ms 376 KB Output is correct
20 Correct 11 ms 320 KB Output is correct
21 Correct 26 ms 376 KB Output is correct
22 Correct 19 ms 384 KB Output is correct
23 Correct 18 ms 332 KB Output is correct
24 Correct 12 ms 332 KB Output is correct
25 Correct 8 ms 332 KB Output is correct
26 Correct 7 ms 332 KB Output is correct
27 Correct 8 ms 316 KB Output is correct
28 Correct 6 ms 332 KB Output is correct
29 Correct 7 ms 364 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Execution timed out 5058 ms 6604 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5088 ms 24700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5093 ms 21772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 16 ms 332 KB Output is correct
8 Correct 14 ms 368 KB Output is correct
9 Correct 17 ms 332 KB Output is correct
10 Correct 8 ms 360 KB Output is correct
11 Correct 7 ms 324 KB Output is correct
12 Correct 9 ms 356 KB Output is correct
13 Correct 8 ms 360 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 13 ms 332 KB Output is correct
16 Correct 16 ms 372 KB Output is correct
17 Correct 8 ms 360 KB Output is correct
18 Correct 19 ms 368 KB Output is correct
19 Correct 15 ms 376 KB Output is correct
20 Correct 11 ms 320 KB Output is correct
21 Correct 26 ms 376 KB Output is correct
22 Correct 19 ms 384 KB Output is correct
23 Correct 18 ms 332 KB Output is correct
24 Correct 12 ms 332 KB Output is correct
25 Correct 8 ms 332 KB Output is correct
26 Correct 7 ms 332 KB Output is correct
27 Correct 8 ms 316 KB Output is correct
28 Correct 6 ms 332 KB Output is correct
29 Correct 7 ms 364 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Execution timed out 5058 ms 6604 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 16 ms 332 KB Output is correct
8 Correct 14 ms 368 KB Output is correct
9 Correct 17 ms 332 KB Output is correct
10 Correct 8 ms 360 KB Output is correct
11 Correct 7 ms 324 KB Output is correct
12 Correct 9 ms 356 KB Output is correct
13 Correct 8 ms 360 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 13 ms 332 KB Output is correct
16 Correct 16 ms 372 KB Output is correct
17 Correct 8 ms 360 KB Output is correct
18 Correct 19 ms 368 KB Output is correct
19 Correct 15 ms 376 KB Output is correct
20 Correct 11 ms 320 KB Output is correct
21 Correct 26 ms 376 KB Output is correct
22 Correct 19 ms 384 KB Output is correct
23 Correct 18 ms 332 KB Output is correct
24 Correct 12 ms 332 KB Output is correct
25 Correct 8 ms 332 KB Output is correct
26 Correct 7 ms 332 KB Output is correct
27 Correct 8 ms 316 KB Output is correct
28 Correct 6 ms 332 KB Output is correct
29 Correct 7 ms 364 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Execution timed out 5058 ms 6604 KB Time limit exceeded
32 Halted 0 ms 0 KB -