#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
static int N, T, S, r, t, s;
static vector<int> W;
vector<int> ask(vector<int> i, vector<int> j) {
++t;
if (t > T)
throw string("Too many queries");
if (i.size() != j.size())
throw string("Invalid query: i and j must have the same size");
int m = i.size();
s += m;
if (s > S)
throw string("Too many total elements in queries");
vector<int> res(m);
for (int k = 0; k < m; k++) {
if (i[k] < 0 || i[k] >= N || j[k] < 0 || j[k] >= N)
throw string("Invalid query: index out of bounds");
res[k] = W[i[k]] > W[j[k]] ? i[k] : j[k];
}
return res;
}
constexpr int Sub2_score = 85;
int main() {
int R;
cin >> N >> T >> S >> R;
if (N <= 0 || T < 0 || S < 0 || R < 0) {
cerr << "Invalid input for N, T, S or R" << endl;
return 1;
}
mt19937_64 rng(R);
W.resize(N);
bool hasWrong = false;
int maxt = 0, maxs = 0;
for (int _ = 0; _ < 10; _++) {
iota(W.begin(), W.end(), 0);
shuffle(W.begin(), W.end(), rng);
int answer = max_element(W.begin(), W.end()) - W.begin();
try {
r = -1; t = 0; s = 0;
r = richest(N, T, S);
if (r != answer)
throw string("Wrong Answer");
cout << r << ' ' << t << ' ' << s << " Correct (pretest)" << endl;
} catch (const string& msg) {
hasWrong = true;
cout << r << ' ' << t << ' ' << s << ' ' << msg << endl;
}
maxt = max(maxt, t);
maxs = max(maxs, s);
}
if (N == 1000 && T == 1 && S == 499500) {
if (hasWrong) {
cout << "Wrong Case 1, score: 0 / " << (100 - Sub2_score) << endl;
} else {
cout << "Correct (pretest) Case 1, score: " << (100 - Sub2_score) << " / " << (100 - Sub2_score) << endl;
}
} else if (N == 1000000 && T == 20 && S == 2000000) {
if (hasWrong) {
cout << "Wrong Case 2, score: 0 / " << Sub2_score << endl;
} else {
double ft = 1;
if (maxt > 8)
ft -= sqrt(maxt - 8) / 4;
double gs = 1;
if (maxs > 1099944) {
if (maxs < 1100044)
gs -= log10(maxs - 1099943) / 6;
else
gs -= 1.0 / 3 + pow(maxs - 1100043, 1.0 / 2) / 1500;
}
cout
<< (ft * gs >= 1 ? "Correct" : "Partially correct")
<< " (pretest) Case 2, score: "
<< to_string(int(Sub2_score * ft * gs))
<< " / " << Sub2_score;
}
} else {
if (hasWrong) {
cout << "Wrong" << endl;
} else {
cout << "Correct" << endl;
}
}
}
#define ll long long
ll id[1005][1005],id2[1000005],ls[10]={500000,250000,125000,62500,20833,3472,183,1};
int richest(int N, int T, int S) {
if (T==1){
vector<int> vct1,vct2;
ll tot=-1;
for (ll i=0;i<N;i++){
for (ll j=i+1;j<N;j++){
vct1.push_back(i);
vct2.push_back(j);
id[i][j]=++tot;
}
}
vector<int> p=ask(vct1,vct2);
for (ll i=0;i<N;i++){
ll c=0;
for (ll j=0;j<N;j++){
if (i!=j){
if (j<i){
c+=p[id[j][i]]==i;
}else{
c+=p[id[i][j]]==i;
}
}
}
if (c==N-1){
return i;
}
}
}
for (ll i=0;i<=N;i++)id2[i]=0;
vector<int> all;
for (ll i=0;i<N;i++)all.push_back(i);
for (ll i=0;i<8;i++){
ll tot=all.size();
vector<vector<int>> vct;
vct.resize(ls[i]+1);
ll ps=0;
for (ll j=0;j<tot;j++){
vct[ps].push_back(all[j]);ps++;ps%=ls[i];
}
vector<int> p1,p2;
for (ll j=0;j<ls[i];j++){
for (ll k=0;k<vct[j].size();k++){
for (ll l=k+1;l<vct[j].size();l++){
p1.push_back(vct[j][k]);p2.push_back(vct[j][l]);
}
}
}
vector<int> p3=ask(p1,p2),p4;
ll rk=-1;
for (ll j=0;j<ls[i];j++){
ll tot2=-1;
for (ll k=0;k<vct[j].size();k++)id2[vct[j][k]]=++tot2;
vector<int> cnt;
cnt.resize(tot2+2);
for (ll k=0;k<vct[j].size();k++){
for (ll l=k+1;l<vct[j].size();l++){
++rk;
assert(rk<p3.size());
cnt[id2[p3[rk]]]++;
}
}
for (ll k=0;k<vct[j].size();k++)if (cnt[id2[vct[j][k]]]==vct[j].size()-1)p4.push_back(vct[j][k]);
}
all=p4;
}
return all[0];
}