Submission #1342304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342304		Jakub_Wozniak	Staring Contest (BOI23_staringcontest)	C++20	100 / 100	4 ms	452 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50009;
int ans[maxn];
int per[maxn];
int perm1[maxn];

int query(int a , int b)
{
    cout << "? " << per[a] << ' ' << per[b] << endl;
    int r;
    cin >> r;
    return r;
}


int main()
{
    srand(time(NULL));
    int n ;
    cin >> n;

    for(int i = 1 ; i <= n ; i++)per[i] = i;
    random_shuffle(per+1,per+n+1);
    for(int i =1; i <= n ; i++)
    {
        perm1[per[i]] = i;
    }

    int i = 1 , j = 2;
    int aktS = query(i,j);
    for(int k = 3; k <= n ; k++)
    {
        int ik = query(i , k);
        if(aktS == ik)
        {
            ans[i] = ik;
            i = k;
            aktS = query(i,j);
        }
        else if(aktS < ik)
        {
            ans[j] = aktS;
            j = k;
            aktS = ik;
        }
        else
        {
            ans[k] = ik;
        }
    }
    ans[i] = aktS;
    ans[j] = aktS;
    cout << "! ";
    for(int i = 1; i <= n ; i++)cout << ans[perm1[i]] << ' ';
    cout << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:19: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = int*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   24 |     random_shuffle(per+1,per+n+1);
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from Main.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 80 / 80