QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#409879	#6776. Garden	ksu_^#	14	1822ms	3944kb	C++23	3.5kb	2024-05-12 20:35:28	2024-05-12 20:35:29

Judging History

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

[2024-05-12 20:35:29]
评测

测评结果：14
用时：1822ms
内存：3944kb

查看

[2024-05-12 20:35:28]
提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

int main(){
    ll n, m, d;
    cin >> n >> m >> d;
    
    vector<pair<ll, ll>> a(n), b(m);
    for(auto &i: a)
        cin >> i.first >> i.second;
    
    for(auto &i: b)
        cin >> i.first >> i.second;
    
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    
    ll ans = d * d;
    for(int a0 = 1; a0 <= d; a0++){
        for(int b0 = 1; b0 <= d; b0++){
            if(a0 * b0 >= ans)
                continue;
            
            bool end0 = false;
            
            for(int i = 0; i < d && !end0; i++){
                for(int j = 0; j < d; j++){
                    bool ok = false;
                    
                    for(auto p: b){
                        if(j % d <= (j + b0 - 1) % d){
                            if(j % d <= p.first && p.first <= (j + b0 - 1) % d)
                                continue;
                        }
                        else{
                            if(p.first >= j % d || p.first <= (j + b0 - 1) % d)
                                continue;
                        }
                        
                        if(i % d <= (i + a0 - 1) % d){
                            if(i % d <= p.second && p.second <= (i + a0 - 1) % d)
                                continue;
                        }
                        else{
                            if(p.second >= i % d || p.second <= (i + a0 - 1) % d)
                                continue;
                        }
                        
                        ok = true;
                        break;
                    }
                    for(auto p: a){
                        bool flag1 = false, flag2 = false;
                        if(j % d <= (j + b0 - 1) % d){
                            if(j % d <= p.first && p.first <= (j + b0 - 1) % d)
                                flag1 = true;
                        }
                        else{
                            if(p.first >= j % d || p.first <= (j + b0 - 1) % d)
                                flag1 = true;
                        }
                        
                        if(i % d <= (i + a0 - 1) % d){
                            if(i % d <= p.second && p.second <= (i + a0 - 1) % d)
                                flag2 = true;
                        }
                        else{
                            if(p.second >= i % d || p.second <= (i + a0 - 1) % d)
                                flag2 = true;
                        }
                        
                        if(!flag1 || !flag2){
                            ok = true;
                            break;
                        }
                    }
                    
                    if(!ok){
                        ans = a0 * b0;
                        end0 = true;
                        break;
                    }
                }
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Time Limit Exceeded

Test #1:

score: 0

Time Limit Exceeded

input:

499986 5 1979
299 1572
1897 274
119 291
206 1287
816 937
1922 1376
1676 57
1106 1706
1534 176
678 606
722 473
399 727
1682 1736
221 506
1413 1857
523 1730
1699 346
1056 1287
801 1017
314 1938
1872 189
1750 581
1846 1937
37 1840
1760 725
1465 1222
678 1203
1422 1930
1273 195
730 1930
232 1666
860 352...

output:

result:

Subtask #2:

score: 6

Accepted

Test #11:

score: 6

Accepted

time: 1ms

memory: 3636kb

input:

output:

result:

ok single line: '12'

Test #12:

score: 0

Accepted

time: 1ms

memory: 3672kb

input:

1759 3239 7
5 5
2 5
3 5
3 5
2 5
1 5
3 5
4 5
5 5
1 5
3 5
5 5
2 5
5 5
5 5
2 5
4 5
1 5
1 5
4 5
2 5
3 5
1 5
4 5
5 5
1 5
2 5
1 5
1 5
3 5
4 5
2 5
1 5
2 5
5 5
2 5
2 5
4 5
3 5
2 5
4 5
5 5
5 5
2 5
3 5
4 5
1 5
2 5
4 5
3 5
3 5
3 5
4 5
5 5
3 5
3 5
1 5
5 5
1 5
3 5
1 5
5 5
4 5
3 5
5 5
3 5
4 5
2 5
5 5
2 5
2 5
2 5
...

output:

result:

ok single line: '5'

Test #13:

score: 0

Accepted

time: 2ms

memory: 3900kb

input:

output:

result:

ok single line: '10'

Test #14:

score: 0

Accepted

time: 2ms

memory: 3672kb

input:

output:

result:

ok single line: '10'

Test #15:

score: 0

Accepted

time: 1ms

memory: 3932kb

input:

output:

result:

ok single line: '9'

Test #16:

score: 0

Accepted

time: 2ms

memory: 3932kb

input:

output:

result:

ok single line: '40'

Test #17:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

output:

result:

ok single line: '70'

Test #18:

score: 0

Accepted

time: 2ms

memory: 3640kb

input:

output:

result:

ok single line: '56'

Test #19:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

output:

result:

ok single line: '100'

Test #20:

score: 0

Accepted

time: 0ms

memory: 3868kb

input:

output:

result:

ok single line: '1'

Test #21:

score: 0

Accepted

time: 0ms

memory: 3900kb

input:

output:

result:

ok single line: '2'

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #22:

score: 8

Accepted

time: 469ms

memory: 3700kb

input:

2098 2896 47
18 20
23 28
6 4
5 4
29 4
21 20
24 17
7 20
21 37
7 37
44 44
23 44
18 37
7 4
4 4
5 26
29 37
16 28
14 20
38 44
29 44
24 17
24 37
21 11
29 11
5 20
5 44
23 26
2 32
7 4
14 4
6 33
7 20
2 44
3 17
16 17
20 4
14 17
16 4
44 17
3 44
16 33
7 11
4 32
18 44
3 44
21 33
23 17
2 26
18 20
4 23
16 44
16 11...

output:

result:

ok single line: '1599'

Test #23:

score: 0

Accepted

time: 152ms

memory: 3932kb

input:

2355 2645 37
24 17
10 35
10 8
24 19
1 0
1 29
20 33
3 36
3 24
1 12
24 14
20 23
10 30
10 35
10 20
3 29
10 20
10 8
24 33
10 0
10 21
24 2
20 25
24 17
1 21
10 26
20 19
1 35
10 17
3 5
24 21
3 23
10 3
24 3
3 26
20 36
24 2
1 14
1 26
3 18
10 5
10 36
20 25
20 31
3 24
3 9
24 21
24 36
10 8
24 2
10 36
10 16
1 9
...

output:

result:

ok single line: '840'

Test #24:

score: 0

Accepted

time: 58ms

memory: 3704kb

input:

output:

result:

ok single line: '50'

Test #25:

score: 0

Accepted

time: 18ms

memory: 3944kb

input:

output:

result:

ok single line: '50'

Test #26:

score: 0

Accepted

time: 12ms

memory: 3940kb

input:

output:

result:

ok single line: '47'

Test #27:

score: 0

Accepted

time: 1822ms

memory: 3636kb

input:

output:

result:

ok single line: '800'

Test #28:

score: 0

Accepted

time: 416ms

memory: 3936kb

input:

output:

result:

ok single line: '1470'

Test #29:

score: 0

Accepted

time: 210ms

memory: 3692kb

input:

output:

result:

ok single line: '1443'

Test #30:

score: 0

Accepted

time: 474ms

memory: 3816kb

input:

output:

result:

ok single line: '2350'

Test #31:

score: 0

Accepted

time: 99ms

memory: 3704kb

input:

output:

result:

ok single line: '2500'

Subtask #4:

score: 0

Time Limit Exceeded

Dependency #3:

100%

Accepted

Test #32:

score: 16

Accepted

time: 773ms

memory: 3936kb

input:

3086 1910 47
7 32
34 32
7 28
8 32
9 17
7 28
43 10
7 32
33 13
24 15
39 10
8 15
30 19
45 15
46 15
44 13
4 28
12 10
41 19
15 13
14 17
16 15
12 17
8 13
30 17
25 10
0 19
4 0
46 13
29 28
4 33
11 17
1 19
27 17
18 0
26 17
18 0
33 0
13 15
36 32
8 17
34 13
33 10
13 10
43 17
46 19
26 32
41 15
16 33
14 17
41 10...

output:

result:

ok single line: '1496'

Test #33:

score: -16

Time Limit Exceeded

input:

4282 718 76
11 11
44 3
64 39
25 35
39 30
40 32
74 42
12 42
64 27
42 43
3 30
23 32
43 53
7 30
53 64
45 30
7 66
45 65
64 13
42 54
59 53
23 53
72 23
16 27
29 66
64 54
64 9
30 2
25 74
39 53
42 43
59 45
36 30
5 11
59 11
59 66
41 52
15 30
29 45
12 64
34 61
65 39
45 39
57 39
34 3
23 43
63 54
64 4
42 27
64 ...