oj.uz

Submission #743268

# Submission time Handle Problem Language Result Execution time Memory
743268 2023-05-17T09:19:05 Z vjudge1 Lightning Rod (NOI18_lightningrod) C++17
40 / 100
 2000 ms 262144 KB 
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<long long, long long>> v;

bool sorted(const pair<long long, long long> &a, const pair<long long, long long> &b)
{
    if (a.second == b.second)
        return a.first > b.first;
    return a.second > b.second;
}

bool check(long long x1,long long x2, long long y1, long long y2)
{
    return abs(x1 - x2) <= y1 - y2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    unordered_map<int, int> ma;
    long long n, a, b;
    cin >> n;
    for (long long i = 1; i <= n; ++i)
    {
        cin >> a >> b;
        v.push_back({a, b});
        ma[i - 1] = -1;
    }
    long long sum = n;
    sort(v.begin(), v.end(), sorted);
    for (long long i = 0; i < v.size(); ++i)
    {
        for (long long j = 0; j < v.size(); ++j)
        {
            if (ma[j] == -1 && i != j && check(v[i].first, v[j].first, v[i].second, v[j].second))
            {
                sum--;
                ma[j] = i;
            }
        }
    }
    cout << sum;
}

Compilation message

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:36:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (long long i = 0; i < v.size(); ++i)
      |                           ~~^~~~~~~~~~
lightningrod.cpp:38:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (long long j = 0; j < v.size(); ++j)
      |                               ~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1123 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 320 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 20 ms 460 KB Output is correct
12 Correct 28 ms 340 KB Output is correct
13 Correct 30 ms 448 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 20 ms 460 KB Output is correct
12 Correct 28 ms 340 KB Output is correct
13 Correct 30 ms 448 KB Output is correct
14 Execution timed out 2033 ms 12596 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1123 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -