oj.uz

Submission #743271

# Submission time Handle Problem Language Result Execution time Memory
743271 2023-05-17T09:19:40 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<long long, long long> 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 941 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 244 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 244 KB Output is correct
11 Correct 24 ms 340 KB Output is correct
12 Correct 28 ms 428 KB Output is correct
13 Correct 32 ms 340 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 244 KB Output is correct
11 Correct 24 ms 340 KB Output is correct
12 Correct 28 ms 428 KB Output is correct
13 Correct 32 ms 340 KB Output is correct
14 Execution timed out 2070 ms 12520 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 906 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 941 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -