QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699014#7696. Forest for the TreesBackToSquare1AC ✓110ms4012kbC++204.0kb2024-11-01 23:45:582024-11-01 23:45:58

Judging History

This is the latest submission verdict.

  • [2024-11-01 23:45:58]
  • Judged
  • Verdict: AC
  • Time: 110ms
  • Memory: 4012kb
  • [2024-11-01 23:45:58]
  • Submitted

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
 
typedef pair<ll, ll> pl;
typedef pair<ld,ld> pd;
typedef vector<ll> vl;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
 
#define G(x) ll x; cin >> x;
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define all(a) begin(a), end(a)
#define K first
#define V second
#define OK(i,j) i >= 0 && i < n && j >= 0 && j < m
 
#define NN 2000005
#define MM 5005
#define MOD 1000000007

void solve() {

    ll nt, ns, rmax;
    cin >> nt >> ns >> rmax;
    vector<pl> trees;
    vector<pl> sensor;
    pl inpt;
    for(ll i=0;i<nt;i++) {
        cin >> inpt.K >> inpt.V;
        trees.push_back(inpt);
    }
    for(ll i=0;i<ns;i++) {
        cin >> inpt.K >> inpt.V;
        sensor.push_back(inpt);
    }

    // pl referenceTree = trees[0];
    // for(ll i=0;i<nt;i++) {
    //     trees[i].K -= referenceTree.K;
    //     trees[i].V -= referenceTree.V;
    // }

    ll valid = 0;
    pl ans = {1e9,1e9};
    sort(sensor.begin(),sensor.end());


    for(ll dir=0;dir<4;dir++) {
        // cout << "DIRECTION " << dir << '\n';
        sort(trees.begin(),trees.end());
        for(ll i=0;i<nt;i++) {

            if(i > 0 && trees[i] == trees[i-1]) continue;
            //place sensor[0] at trees[i]
            //ensure there is no tree at trees[i] - sensor[0]
            pl robotLoc = {trees[i].K-sensor[0].K,trees[i].V-sensor[0].V};
            // cout << "I AM CONSIDERING (" << robotLoc.K << ',' << robotLoc.V << ")\n";
            auto closestTree = lower_bound(trees.begin(),trees.end(),robotLoc);
            if(closestTree != trees.end() && *closestTree == robotLoc) continue;
            // cout << "VALID START LOCATION\n";

            ll j1=0, j2=1;
            bool ok = 1;

            while(j1 < i) {
                if((abs(trees[j1].K - robotLoc.K)) + (abs(trees[j1].V-robotLoc.V)) <= rmax) {
                    ok = 0;
                    // cout << "PRECHECK: FAILED FOR TREE (" << trees[j1].K << ',' << trees[j1].V << ")\n";
                }
                j1++;
            }

            j1++;

            if(!ok) continue;

            while(j1<nt && j2<ns) {
                // is trees[j1] in range?
                if((abs(trees[j1].K - robotLoc.K)) + (abs(trees[j1].V-robotLoc.V)) > rmax) {
                    j1++;
                    continue;
                }

                pl treeLoc = {robotLoc.K + sensor[j2].K,robotLoc.V + sensor[j2].V};
                if(trees[j1] == treeLoc) {
                    j1++;
                    j2++;
                }
                else {
                    ok = 0;
                    break;
                }
            }
            if(j2 < ns) ok = 0;

            while(j1 < nt) {
                if((abs(trees[j1].K - robotLoc.K)) + (abs(trees[j1].V-robotLoc.V)) <= rmax) {
                    ok = 0;
                    // cout << "POSTCHECK: FAILED FOR TREE (" << trees[j1].K << ',' << trees[j1].V << ")\n";
                }
                j1++;
            }

            if(!ok) continue;

            valid++;

            if(dir == 0) ans = robotLoc;
            else if(dir == 1) ans = {robotLoc.V,-robotLoc.K};
            else if(dir == 2) ans = {-robotLoc.K,-robotLoc.V};
            else ans = {-robotLoc.V,robotLoc.K};

            if(valid > 1) break;
        }
        if(valid > 1) break;
        for(ll i=0;i<nt;i++) {
            //rotate grid
            trees[i] = {-trees[i].V,trees[i].K};
        }
    }

    if(valid == 0) cout << "Impossible\n";
    else if(valid == 1) cout << ans.K << ' ' << ans.V << '\n';
    else cout << "Ambiguous\n";

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    solve();

    return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

4 4 100
1 1
2 2
2 1
3 3
0 1
0 2
-1 2
-2 3

output:

0 1

result:

ok single line: '0 1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

4 4 4
0 1
1 0
0 -1
-1 0
0 1
1 0
0 -1
-1 0

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #3:

score: 0
Accepted
time: 51ms
memory: 3768kb

input:

4899 957 32
-9961 -9999
-9970 -9968
-9942 -9986
-9991 -9991
-9950 -9990
-9958 -9994
-9939 -9944
-9992 -9987
-9973 -9937
-9981 -9941
-9940 -9940
-9989 -9945
-9961 -9963
-9970 -9932
-9969 -9967
-9977 -9971
-9949 -9989
-9958 -9958
-9957 -9993
-9937 -9935
-9938 -9980
-9965 -9997
-9992 -9951
-9946 -9984
...

output:

-9929 -9959

result:

ok single line: '-9929 -9959'

Test #4:

score: 0
Accepted
time: 5ms
memory: 4012kb

input:

4899 941 40
-9970 -9968
-9942 -9986
-9991 -9991
-9950 -9990
-9958 -9994
-9939 -9944
-9992 -9987
-9973 -9937
-9981 -9941
-9940 -9940
-9989 -9945
-9961 -9963
-9970 -9932
-9969 -9967
-9977 -9971
-9949 -9989
-9958 -9958
-9957 -9993
-9937 -9935
-9938 -9980
-9965 -9997
-9992 -9951
-9946 -9984
-10000 -9955...

output:

Impossible

result:

ok single line: 'Impossible'

Test #5:

score: 0
Accepted
time: 5ms
memory: 3772kb

input:

4899 940 40
-9970 -9968
-9942 -9986
-9991 -9991
-9950 -9990
-9958 -9994
-9939 -9944
-9992 -9987
-9973 -9937
-9981 -9941
-9940 -9940
-9989 -9945
-9961 -9963
-9970 -9932
-9969 -9967
-9977 -9971
-9949 -9989
-9958 -9958
-9957 -9993
-9937 -9935
-9938 -9980
-9965 -9997
-9992 -9951
-9946 -9984
-10000 -9955...

output:

Impossible

result:

ok single line: 'Impossible'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

3 3 1000
1 0
0 1
1 1
1 0
0 1
1 1

output:

0 0

result:

ok single line: '0 0'

Test #7:

score: 0
Accepted
time: 71ms
memory: 3708kb

input:

5000 2 1000
0 0
1000 1000
66740 84615
-16851 37613
31009 31589
-68041 -71122
21568 86889
53743 -31217
-73472 63365
9594 -12742
-25497 -5264
15942 13442
19537 -83361
93129 67319
-27565 73861
75273 -19266
-55048 -79726
-45975 -36987
-51309 35820
-99049 -10933
-45867 99815
-52121 99729
-89976 -15892
38...

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #8:

score: 0
Accepted
time: 110ms
memory: 3932kb

input:

5000 3 1000
0 0
1000 1000
1000 999
13954 9751
75888 -54632
10747 -12901
37707 -37988
-49564 26056
-30528 -9620
6227 -95560
-82768 85135
-15530 89254
-39739 -79664
-81590 -75580
91135 -20238
-52264 -66253
-41259 -90627
-7096 -35158
-67316 13384
79722 57595
-40566 99205
35854 -48598
-83531 -59472
-286...

output:

600 400

result:

ok single line: '600 400'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4 3 100
1 1
2 2
2 1
3 3
0 1
0 2
-1 2

output:

Impossible

result:

ok single line: 'Impossible'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

3 3 100
1 1
2 1
3 1
0 1
0 2
0 3

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

4 3 2
1 1
2 2
2 1
3 3
0 1
0 2
-1 1

output:

2 0

result:

ok single line: '2 0'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

121 121 50
4 0
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 ...

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

120 120 50
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 2
4 ...

output:

5 5

result:

ok single line: '5 5'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

120 119 50
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 2
4 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

121 121 50
4 0
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 ...

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #16:

score: 0
Accepted
time: 32ms
memory: 3644kb

input:

2598 217 20
-28 50
-36 46
-16 24
-24 20
50 6
-44 -38
42 2
6 48
-42 8
-50 4
-30 -18
-38 -22
-20 26
-18 -44
-38 14
2 50
-46 10
-18 -8
22 28
-26 -12
14 24
-34 -16
-6 -34
-14 -38
26 -2
-22 -42
18 -6
-4 12
36 48
-12 8
8 -14
48 22
0 -18
18 30
-8 -22
20 -40
12 -44
30 4
4 -48
-8 14
12 -8
4 -12
44 24
24 -34
...

output:

5 5

result:

ok single line: '5 5'