QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569651#8267. Staring ContestKeklord19450 1ms12100kbC++234.0kb2024-09-17 03:19:492024-09-17 03:19:49

Judging History

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

  • [2024-09-17 03:19:49]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:12100kb
  • [2024-09-17 03:19:49]
  • 提交

answer

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

#ifdef natural_selection
#include "/dbg.h"
#else
#define endl "\n"
#define debug(...)
#endif

struct Random : std::mt19937
{
    using std::mt19937::mt19937;
    using std::mt19937::operator();
    static int64_t gen_seed()
    {
        return std::chrono::steady_clock::now().time_since_epoch().count();
    }
    Random() : std::mt19937(gen_seed()) {}
    template <class Int>
    auto operator()(Int a, Int b)
        -> std::enable_if_t<std::is_integral_v<Int>, Int>
    {
        return std::uniform_int_distribution<Int>(a, b)(*this);
    }
    template <class Int>
    auto operator()(Int a) -> std::enable_if_t<std::is_integral_v<Int>, Int>
    {
        return std::uniform_int_distribution<Int>(0, a - 1)(*this);
    }
    template <class Real>
    auto operator()(Real a, Real b)
        -> std::enable_if_t<std::is_floating_point_v<Real>, Real>
    {
        return std::uniform_real_distribution<Real>(a, b)(*this);
    }
};

const int N = 1500, B = 86400;  

int val[N][N];

int32_t main()
{
    Random rng;

    int n;
    cin >> n;

    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    random_shuffle(a.begin(), a.end(), rng);

    auto ask = [&](int u, int v) -> int
    {
        // assert(u != v);
        if(val[u][v] == 0)
        {
            cout << "?" << " " << u + 1 << " " << v + 1 << endl;
            cin >> val[u][v];
            val[v][u] = val[u][v];
        }
        return val[u][v];
    };

    vector<int> ans(n, B);
    while((int)a.size() >= 4)
    {
        // assert((int)a.size() >= 4); ok
        
        vector<int> b(4);
        for(int i = 0; i < 4; i ++) 
            b[i] = a.back(), a.pop_back();
        
        random_shuffle(b.begin(), b.end(), rng);

        vector<int> f(4, B);
        for(int i = 0; i < 4; i ++)
            f[i] = ask(b[i], b[(i + 1) % 4]);

        int cnt = set<int>(f.begin(), f.end()).size();
        if(cnt == 2)
        {
            for(int i = 0; i < 4; i ++)
                if(f[i] == f[(i - 1 + 4) % 4])
                    ans[b[i]] = f[i];
            
            int ins = 0;
                for(int i = 0; i < 4; i ++)
                    if(ans[b[i]] == B)
                        ++ ins, a.push_back(b[i]);
                // assert(ins == 2);
        }
        else if(cnt == 3)
        {
            int mn = *min_element(f.begin(), f.end());
            int mx = *max_element(f.begin(), f.end());

            for(int i = 0; i < 4; i ++)
            {
                if(f[i] == f[(i - 1 + 4) % 4])
                    ans[b[i]] = f[i];
                else if(f[i] != mn and f[i] != mx)
                {
                    if(f[(i - 1 + 4) % 4] == mn)
                        ans[b[i]] = f[i];
                    if(f[(i + 1) % 4] == mn)
                        ans[b[(i + 1) % 4]] = f[i];
                }

                int ins = 0;
                for(int i = 0; i < 4; i ++)
                    if(ans[b[i]] == B)
                        ++ ins, a.push_back(b[i]);
                //assert(ins == 2);
            }
        }
    }

    if((int)a.size() == 3)
    {
        vector<int> b(3);
        for(int i = 0; i < 3; i ++) 
            b[i] = a.back(), a.pop_back();
        
        random_shuffle(b.begin(), b.end(), rng);

        vector<int> f(3, B);
        for(int i = 0; i < 3; i ++)
            f[i] = ask(b[i], b[(i + 1) % 3]);

        int m = *min_element(f.begin(), f.end());
        for(int i = 0; i < 3; i ++)
        {
            if(f[i] != m)
            {
                if(a.empty())
                    ans[b[i]] = ans[b[(i + 1) % 3]] = f[i];
                else
                    a.push_back(b[i]), a.push_back(b[(i + 1) % 3]);
                ans[b[(i - 1 + 3) % 3]] = m;
            }
        }
    }
    else if((int)a.size() == 2)
        ans[a[0]] = ans[a[1]] = ask(a[0], a[1]);

    cout << "!" << " ";
    for(auto x : ans)
        cout << x << " ";
    cout << endl;
}

/*
4 5 3 2 6 8

*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 9
Accepted
time: 1ms
memory: 3812kb

input:

2
1

output:

? 2 1
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #2:

score: 9
Accepted
time: 1ms
memory: 3608kb

input:

2
1

output:

? 1 2
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #3:

score: 9
Accepted
time: 1ms
memory: 3616kb

input:

2
1

output:

? 1 2
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 3932kb

input:

50
13
13
44
38
38
13
8
11
8
44
46
11
2
2
18
4
4
4
37
18
15
23
15
23
14
28
28
14
6
40
3
3
3
40
41
5
5
41
34
34
21
21
35
19
19
35
42
42
10
10
43
43
20
20
26
26
33
45
45
48
33
26
27
29
12
12
12
29
9
29
17
9
17
39
16
16
36
17
36
1
25
16
1
49
25
7
22
47
31
31
24
49
24
50
30

output:

? 38 13
? 13 44
? 44 46
? 46 38
? 38 44
? 46 13
? 8 44
? 46 11
? 11 8
? 44 44
? 46 46
? 44 11
? 4 2
? 2 37
? 37 18
? 18 4
? 4 4
? 37 4
? 37 37
? 18 18
? 15 37
? 37 23
? 23 15
? 23 23
? 14 40
? 40 28
? 28 41
? 41 14
? 6 41
? 41 40
? 40 3
? 3 6
? 3 41
? 40 40
? 41 41
? 42 5
? 5 41
? 41 42
? 42 34
? 34...

result:

wrong answer wrong answer b[36] <= a[36] not held.

Subtask #2:

score: 0
Wrong Answer

Test #58:

score: 0
Wrong Answer
time: 0ms
memory: 9212kb

input:

1000
378
378
656
656
57
57
297
790
856
790
297
57
243
681
806
229
229
856
229
150
349
427
150
907
427
674
349
347
75
510
777
797
567
696
696
780
98
70
51
51
98
51
51
272
70
98
410
272
37
37
272
470
470
829
829
831
852
365
365
365
996
357
852
160
160
160
160
952
583
327
327
583
450
450
421
421
585
45...

output:

? 790 378
? 378 856
? 856 656
? 656 790
? 856 57
? 57 297
? 297 790
? 790 856
? 856 856
? 790 790
? 856 297
? 57 790
? 856 243
? 856 681
? 806 856
? 856 229
? 229 806
? 907 856
? 229 907
? 150 349
? 349 427
? 427 907
? 907 150
? 907 907
? 427 427
? 907 674
? 907 349
? 907 347
? 907 75
? 510 907
? 90...

result:

wrong answer wrong answer b[455] <= a[455] not held.

Subtask #3:

score: 0
Wrong Answer

Test #88:

score: 0
Wrong Answer
time: 0ms
memory: 12100kb

input:

1500
385
385
68
68
757
228
228
757
437
776
387
387
387
776
1390
1390
1491
776
1491
1499
288
1241
1241
288
401
1190
912
401
1240
1190
912
1234
528
360
360
360
1376
1039
226
226
226
45
1373
1039
45
1373
221
221
417
918
1145
417
918
221
1058
874
448
448
874
920
42
42
920
203
932
970
203
1307
970
79
79
...

output:

? 1390 385
? 385 757
? 757 68
? 68 1390
? 757 1390
? 1390 228
? 228 776
? 776 757
? 437 1390
? 1390 776
? 776 387
? 387 437
? 387 1390
? 776 776
? 1390 1390
? 1390 1491
? 1491 1499
? 1499 776
? 1491 1491
? 1499 1499
? 288 1499
? 1499 1241
? 1241 1491
? 1491 288
? 401 1190
? 1190 1240
? 1240 912
? 91...

result:

wrong answer wrong answer b[558] <= a[558] not held.