Submission #1178183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178183		8pete8	Minerals (JOI19_minerals)	C++17	75 / 100	27 ms	3660 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;
pii bound[mxn+10];
int P[mxn+10],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 mid=(L.size()-1)/2;
  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(ask(i)==k)r1.pb(i);
    else r2.pb(i);
  }
  dnc(l1,r1,!k);
  dnc(l2,r2,k);
}
void Solve(int N){
  n=N;
  for(int i=1;i<=2*n;i++)P[i]=i;
  for(int i=1;i<=2*n;i++)swap(P[i],P[1+rng()%i]);
  vector<int>L,R;
  for(int i=1;i<=2*n;i++){
    if(ask(P[i])){
      L.pb(P[i]);
    }
    else R.pb(P[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:23:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | int ask(int x){
      |              ^
minerals.cpp:31:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   31 | void dnc(vector<int>L,vector<int>R,int k){
      |                                         ^
minerals.cpp:46:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | 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: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10