Submission #603305

#	Time	Username	Problem	Language	Result	Execution time	Memory
603305		DanerZein	Art Collections (BOI22_art)	C++17	35 / 100	211 ms	7616 KiB

art

#include "art.h"
#include <bits/stdc++.h>
using namespace std;

map<vector<int>,int> que;
int cost(vector<int> x,int i,int j){
  x.erase(x.begin()+j);
  x.insert(x.begin()+i,j+1);
  if(que.find(x)!=que.end()) return que[x];
  return que[x]=publish(x);
}
void solve(int N) {
  vector<int> ord;
  for(int i=1;i<=N;i++) ord.push_back(i);
  for(int i=1;i<N;i++){
    int l=0,r=i;
    while(r-l>2){
      int m1=l+(r-l)/3;
      int m2=r-(r-l)/3;
      int c1=cost(ord,m1,i);
      if(c1==0){
	ord.erase(ord.begin()+i);
	ord.insert(ord.begin()+m1,i+1);
	answer(ord);
	return;
      }
      int c2=cost(ord,m2,i);
      if(c2==0){
	ord.erase(ord.begin()+i);
	ord.insert(ord.begin()+m2,i+1);
	answer(ord);
	return;
      }
      if(c1>c2){
	l=m1;
      }
      if(c2>c1){
	r=m2;
      }
      if(c1==c2){
	l=m1; r=m2;
      }
    }
    int mi=1e9;
    int id=-1;
    for(int j=l;j<=r;j++){
      int rp=cost(ord,j,i);
      if(rp<mi){
	mi=rp;
	id=j;
      }
      if(rp==0) break;
    }
    ord.erase(ord.begin()+i);
    ord.insert(ord.begin()+id,i+1);
    if(mi==0) break;
  }
  answer(ord);
}

Compilation message (stderr)

interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30