QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569674#8267. Staring ContestKeklord19450 2ms10840kbC++234.2kb2024-09-17 04:12:542024-09-17 04:12:55

Judging History

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

  • [2024-09-17 04:12:55]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:10840kb
  • [2024-09-17 04:12:54]
  • 提交

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], now=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];
                }

                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 << now<< 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: 3540kb

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #2:

score: 9
Accepted
time: 0ms
memory: 3556kb

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

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

input:

50
37
37
42
42
20
3
3
47

output:

? 50 37
? 37 47
? 47 42
? 42 50
? 47 20
? 20 3
? 3 50
? 50 47
2003030470002030-1
2003030470002030-1
? 50 23

result:

wrong answer unknown command 2003030470002030-1

Subtask #2:

score: 0
Wrong Answer

Test #58:

score: 0
Wrong Answer
time: 2ms
memory: 10840kb

input:

1000
86
372
372
86
617
489
489
617
624
624
343
343
935
646
646
882

output:

? 86 489
? 489 372
? 372 882
? 882 86
? 617 882
? 882 489
? 489 935
? 935 617
? 935 624
? 624 882
? 882 343
? 343 935
? 935 999
? 999 646
? 646 882
? 882 935
9350646064608820001020-1
9350646064608820001020-1
93506460646088200010302
? 999 999

result:

wrong answer unknown command 9350646064608820001020-1

Subtask #3:

score: 0
Runtime Error

Test #88:

score: 0
Runtime Error

input:

1500
1172
1172
943
943
1339
294
294
1339
1368
1364
406
406

output:

? 1339 1172
? 1172 1400
? 1400 943
? 943 1339
? 1339 1400
? 1400 294
? 294 1368
? 1368 1339
? 1368 1400
? 1400 1364
? 1364 406
? 406 1368
136801364040604060001020-1
136801364040604060001030-1
136801364040604060001030-1
? 406 1400

result: