QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569667#8267. Staring ContestKeklord19450 1ms10804kbC++234.2kb2024-09-17 03:58:192024-09-17 03:58:19

Judging History

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

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

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 = 1505, B = 86401;  

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());
int now=-1;
            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], now=b[i];
                    if(f[(i + 1) % 4] == mn)
                        ans[b[(i + 1) % 4]] = f[i];
                }

                vector<int>ins;
                for(int i = 0; i < 4; i ++)
                    if(ans[b[i]] == B)
                        ins.push_back(i), a.push_back(b[i]);
                //assert(ins == 2);
if(ins.size()!=2) cout << f[0] << 0 << f[1] << 0 << f[2] << 0 << f[3] << 0 << ins[0] << 0 << ins[1] << 0 << ins[2] << 0 << b[i] << endl;
            }
        }
    }

    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: 3608kb

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: 0ms
memory: 3692kb

input:

2
1

output:

? 2 1
! 1 1 

result:

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

Test #3:

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

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: 1ms
memory: 4060kb

input:

50
35
35
12
12
9
21
38
9

output:

? 40 35
? 35 38
? 38 12
? 12 40
? 9 21
? 21 40
? 40 38
? 38 9
90210380901020308
? 38 38

result:

wrong answer unknown command 90210380901020308

Subtask #2:

score: 0
Wrong Answer

Test #58:

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

input:

1000
179
618
574
179

output:

? 179 930
? 930 618
? 618 574
? 574 179
1790618057401790102030178
1790618057401790102030929
? 930 930

result:

wrong answer unknown command 1790618057401790102030178

Subtask #3:

score: 0
Wrong Answer

Test #88:

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

input:

1500
555
555
994
783

output:

? 783 555
? 555 994
? 994 1034
? 1034 783
5550555099407830001020782
5550555099407830002030554
5550555099407830002030993
? 994 783

result:

wrong answer unknown command 5550555099407830001020782