QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87713#2365. Flight CollisionBitrollTL 24ms7684kbC++172.9kb2023-03-14 03:34:082023-03-14 03:34:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 03:34:09]
  • 评测
  • 测评结果:TL
  • 用时:24ms
  • 内存:7684kb
  • [2023-03-14 03:34:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

// debug util
#ifdef DEBUG
    #define deb(x) cerr << #x << " = " << x << endl
#else
    #define deb(x)
#endif

// useful
#define ll long long
#define umap unordered_map
bool multi = false;

void solve(){

    int n;
    cin >> n;

    //array<array<int,2>,n> dro = {};
    int dro[n][3];
    list<int> ld;

    // get input, add to list 
    for (int i = 0; i < n; i++){
        cin >> dro[i][0] >> dro[i][1];
        dro[i][2] = 1;
        ld.push_back(i);
    }

    // check each paur until there is no more positive numbers
    //while(true){

        multiset<vector<long double>> ts;
        bool finished = true;

        // save time to temporary list
        //for (int i = 0; i < n-1; i++){
        int i = -1;
        int j = -1;
        for (list<int>::iterator it = ld.begin(); it != ld.end(); it++){
            
            if (it == ld.begin()){
                j = *it;
                continue;
            }
            i = j;
            j = *it;
            long double time = 0;


            // different speed
            if (dro[i][1] == dro[j][1])
                continue;

            time = ((long double)(dro[i][0] - dro[j][0])) / (dro[j][1] - dro[i][1]);
            if (time <= 0) continue;
            finished = false;

            ts.insert({time, (long double)i, (long double)j});
            i = *it;
        }

		bool potentialCol = true;
		
		//while (potentialCol){
			//potentialCol = false;
			deb(1);
			// iterate each item in the list
			for (multiset<vector<long double>>::iterator it = ts.begin(); it != ts.end(); it++)
			{
				vector<long double> v = *it;
				deb("collision");
				int v1 = (int)v[1];
				int v2 = (int)v[2];
				deb(v[0]);
				deb(v[1]);
				deb(v[2]);

				// check they still exists

				if (!(dro[v1][2] && dro[v2][2])){
					finished = false;
					continue;
				}
				
				// only bigger than 0
				if (v[0] <= 0)
					continue;

				dro[v1][2] = 0;
				dro[v2][2] = 0;

				// remove from list
				ld.remove(v1);
				ld.remove(v2);
				deb("removed");
				
				// calculate time for new adjacente nodes
				v1--;
				v2++;
				if ((v1 >= 0) && (v2 < n)){
					it = ts.begin();
					
					// different speed
					if (dro[v1][1] == dro[v2][1])
						continue;

					long double time = ((long double)(dro[v1][0] - dro[v2][0])) / (dro[v2][1] - dro[v1][1]);
					if (time <= 0) continue;
					//finished = false;

					ts.insert({time, (long double)v1, (long double)v2});
					//potentialCol = true;
					
					
					//break;
				}
				

			}
		//}

        //if (finished) break;
    //}

    // print solution
    cout << ld.size() << endl;
    for (list<int>::iterator it = ld.begin(); it != ld.end(); it++){
        int i = *it;
        cout << i+1 << " ";
    }
    cout << endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    if(multi)cin>>t;
    while(t--)solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3384kb

input:

1
-4 13

output:

1
1 

result:

ok 2 lines

Test #2:

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

input:

5
1 1000000000
2 1000000000
3 -1000000000
4 -1000000000
5 -1000000000

output:

1
5 

result:

ok 2 lines

Test #3:

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

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3 

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

2
5 4
10 5

output:

2
1 2 

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

9
10 10
20 7
30 5
40 0
42 0
50 -1
60 -2
70 -10
80 -12

output:

1
1 

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

5
10 0
20 0
30 1
40 0
50 0

output:

3
1 2 5 

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 24ms
memory: 7684kb

input:

98765
0 -48539
1 -48539
2 -48539
3 -48539
4 -48539
5 -48539
6 -48539
7 -48539
8 -48539
9 -48539
10 -48539
11 -48539
12 -48539
13 -48539
14 -48539
15 -48539
16 -48539
17 -48539
18 -48539
19 -48539
20 -48539
21 -48539
22 -48539
23 -48539
24 -48539
25 -48539
26 -48539
27 -48539
28 -48539
29 -48539
30 -...

output:

98765
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok 2 lines

Test #8:

score: -100
Time Limit Exceeded

input:

99999
-999999396 999999395
-999971669 999999396
-999971668 -999999396
-999961260 999999396
-999961259 -999999396
-999907239 999999396
-999907238 -999999396
-999754561 999999396
-999754560 -999999396
-999662011 999999396
-999662010 -999999396
-999651505 999999396
-999651504 -999999396
-999619141 9999...

output:


result: