Submission #1178193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178193		8pete8	Minerals (JOI19_minerals)	C++17	100 / 100	38 ms	4016 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
const ll inf=1e9,mxn=1e5;
int last=0;
int n;

int ask(int x){
  int y=Query(x);
  int g=(last!=y);
  last=y;
  return g;
}

mt19937 rng(time(NULL));
void dnc(vector<int>L,vector<int>R,int k){
  if(L.size()==1)return void(Answer(L[0],R[0]));
  if(L.empty())return;
  int sz=L.size();
  int mid=(sz-1)*0.4;
  for(int i=0;i<sz;i++)swap(R[i],R[rng()%(i+1)]);
  vector<int>l1,r1,l2,r2;
  
  for(int i=0;i<=mid;i++)l1.pb(L[i]),ask(L[i]);
  for(int i=mid+1;i<L.size();i++)l2.pb(L[i]);

  for(auto i:R){
    if(r1.size()!=(mid+1)&&(r2.size()==(sz-mid-1)||ask(i)==k))r1.pb(i);
    else r2.pb(i);
  }
  dnc(l1,r1,!k);
  dnc(l2,r2,k);
}
void Solve(int N){
  n=N;
  vector<int>L,R;
  for(int i=1;i<=2*n;i++){
    if(ask(i)){
      L.pb(i);
    }
    else R.pb(i);
  }
  dnc(L,R,1);
}
/*
p bs?
*/

Compilation message (stderr)

minerals.cpp:17:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   17 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
minerals.cpp:22:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   22 | int ask(int x){
      |              ^
minerals.cpp:30:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   30 | void dnc(vector<int>L,vector<int>R,int k){
      |                                         ^
minerals.cpp:48:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | void Solve(int N){
      |                 ^

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10