Submission #1143616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143616		owoovo	Monster Game (JOI21_monster)	C++20	0 / 100	23 ms	416 KiB

monster

#include "monster.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
vector<int> Solve(int N) {
  int n=N;
  vector<int> id(n);
  for(int i=0;i<n;i++)id[i]=i;
  auto mg=[&](auto MG,int l,int r){
    if(l==r)return;
    int m=(l+r)>>1;
    MG(MG,l,m);
    MG(MG,m+1,r);
    // cout<<"at "<<l<<" "<<m<<" "<<r<<"\n";
    // for(int i=l;i<=m;i++){
    //   cout<<id[i]<<" ";
    // }
    // cout<<"\n";
    // for(int i=m+1;i<=r;i++){
    //   cout<<id[i]<<" ";
    // }
    // cout<<"\n";
    vector<int> nw;
    int lp=l,rp=m+1;
    while(lp!=m+1&&rp!=r+1){
      if(Query(id[lp],id[rp])){
        nw.push_back(id[rp]);
        rp++;
      }else{
        nw.push_back(id[lp]);
        lp++;
      }
    }
    while(lp!=m+1){
      nw.push_back(id[lp]);
      lp++;
    }
    while(rp!=r+1){
      nw.push_back(id[rp]);
      rp++;
    }
    for(int i=l;i<=r;i++){
      // cout<<nw[i-l]<<" ";
      id[i]=nw[i-l];
    }
    // cout<<"\n";
    return;
  };
  mg(mg,0,n-1);
  // for(auto x:id){
  //   cout<<x<<" ";
  // }
  // cout<<"\n";
  if(Query(id[0],id[2])||Query(id[0],id[3]))swap(id[0],id[1]); 
  for(int i=2;i<n;i++){
    if(Query(id[i-2],id[i]))swap(id[i],id[i-1]);
  }
  // cout<<"?\n";
  vector<int> ans(n);
  for(int i=0;i<n;i++){
    ans[id[i]]=i;
  }
  // for(auto x:id){
  //   cout<<x<<" ";
  // }
  // cout<<"\n";
  // for(auto x:ans){
  //   cout<<x<<" ";
  // }
  // cout<<Query(2,0)<<"\n";
  return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75