oj.uz

Submission #94047

# Submission time Handle Problem Language Result Execution time Memory
94047 2019-01-15T03:49:14 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 21724 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ 305555
int n;
//B块
#define pb push_back
typedef pair<int,int> pii;
#define fi first
#define se second
int B=100,G=0;
vector<int> bl[SZ];
vector<int> seq;
int be[SZ],x[SZ],W,blk[SZ];
struct scmp
{
bool operator () (int a,int b)
{
	return (x[a]!=x[b])?(x[a]<x[b]):(a<b);
}
};
set<int,scmp> ns;
int ts[SZ];
int* getseq()
{
	int tn=0;
	for(auto t:seq)
		for(int j=0;j<bl[t].size();++j)
			ts[tn++]=bl[t][j];
	return ts;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
inline void reset_block(vector<int>&v_)
{
	int j=0,vn=v_.size(),*v=v_.data();
	for(int i=0;i<vn;++i)
	{
		while(j<vn&&x[v[j]]<=x[v[i]]+W) ++j;
		if(j==vn) j1[v[i]]=-1;
		else j1[v[i]]=v[j];
	}
	for(int i=int(vn)-1;i>=0;--i)
		if(j1[v[i]]==-1) js[v[i]].fi=v[i],js[v[i]].se=0;
		else
			js[v[i]].fi=js[j1[v[i]]].fi,
			js[v[i]].se=js[j1[v[i]]].se+1;
}
inline void rebuild(int*v)
{
	int u=int(n)/B;
	if(!u) ++u;
	for(int i=1;i<=G;++i) bl[i].clear();
	seq.clear(); G=0;
	vector<int> p; p.reserve(u);
	for(int i=0;i<n;++i)
	{
		p.pb(v[i]);
		if(p.size()>=u||i==n-1)
		{
			bl[++G]=p,reset_block(p);
			for(auto t:p) blk[t]=G;
			seq.pb(G),p.clear();
			p.reserve(u);
		}
	}
}
inline int ask()
{
	int s=*ns.begin(),cn=0;
	while(1)
	{
		if(js[s].se)
			cn+=js[s].se,s=js[s].fi;
		x[SZ-1]=x[s]+W;
		auto u=ns.lower_bound(SZ-1);
		++cn; if(u==ns.end()) break; s=*u;
	}
	return cn;
}
int cnt=0;
void init(int N, int L_, int X[])
{
	n=N; W=L_;
	for(int i=0;i<n;++i) x[i]=X[i];
	vector<int> v;
	for(int i=0;i<n;++i)
		v.pb(i),ns.insert(i);
	rebuild(v.data());
}
int update(int t,int y)
{
	ns.erase(t);
	{
		int i=blk[t];
		vector<int>&B=bl[i];
		for(int j=0;;++j)
			if(B[j]==t)
			{
				for(int k=j;k+1<B.size();++k)
					B[k]=B[k+1];
				B.pop_back(); break;
			}
		if(B.size()) reset_block(B);
		else
		{
			for(int j=0;;++j)
				if(seq[j]==i)
				{
					for(int k=j;k+1<seq.size();++k)
						seq[k]=seq[k+1];
					seq.pop_back(); break;
				}
		}
	}
	x[t]=y; ns.insert(t);
	for(int i=0;i<int(seq.size());++i)
		if(x[t]<=x[bl[seq[i]].back()]||i+1==int(seq.size()))
		{
			while(x[bl[seq[i]].back()]<=x[t]
			&&i+1!=int(seq.size())&&rand()%3) ++i;
			static int us[SZ]; int un=0;
			vector<int> &s=bl[seq[i]]; bool c=0;
			for(int j=0;j<s.size();++j)
			{
				if(x[s[j]]>x[t])
				{if(!c) us[un++]=t; c=1;}
				us[un++]=s[j];
			}
			if(!c) us[un++]=t; s.pb(0);
			for(int i=0;i<un;++i) s[i]=us[i];
			reset_block(s); blk[t]=seq[i];
			break;
		}
	++cnt;
	if(cnt%(B*2)==0) rebuild(getseq());
	return ask();
}

Compilation message

elephants.cpp: In function 'int* getseq()':
elephants.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<bl[t].size();++j)
               ~^~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild(int*)':
elephants.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p.size()>=u||i==n-1)
      ~~~~~~~~^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k+1<B.size();++k)
                 ~~~^~~~~~~~~
elephants.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=j;k+1<seq.size();++k)
                  ~~~^~~~~~~~~~~
elephants.cpp:125:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:131:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:131:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(!c) us[un++]=t; s.pb(0);
                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7548 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7548 KB Output is correct
4 Correct 8 ms 7532 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7548 KB Output is correct
4 Correct 8 ms 7532 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 452 ms 9408 KB Output is correct
8 Correct 569 ms 9920 KB Output is correct
9 Correct 1071 ms 12352 KB Output is correct
10 Correct 1163 ms 12116 KB Output is correct
11 Correct 1147 ms 12148 KB Output is correct
12 Correct 2242 ms 12348 KB Output is correct
13 Correct 2033 ms 12192 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7548 KB Output is correct
4 Correct 8 ms 7532 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 452 ms 9408 KB Output is correct
8 Correct 569 ms 9920 KB Output is correct
9 Correct 1071 ms 12352 KB Output is correct
10 Correct 1163 ms 12116 KB Output is correct
11 Correct 1147 ms 12148 KB Output is correct
12 Correct 2242 ms 12348 KB Output is correct
13 Correct 2033 ms 12192 KB Output is correct
14 Correct 649 ms 9992 KB Output is correct
15 Correct 1061 ms 10484 KB Output is correct
16 Correct 3318 ms 12680 KB Output is correct
17 Correct 4219 ms 14240 KB Output is correct
18 Correct 4080 ms 14288 KB Output is correct
19 Correct 2708 ms 13928 KB Output is correct
20 Correct 3988 ms 14160 KB Output is correct
21 Correct 3892 ms 14420 KB Output is correct
22 Correct 3092 ms 13924 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7548 KB Output is correct
4 Correct 8 ms 7532 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 452 ms 9408 KB Output is correct
8 Correct 569 ms 9920 KB Output is correct
9 Correct 1071 ms 12352 KB Output is correct
10 Correct 1163 ms 12116 KB Output is correct
11 Correct 1147 ms 12148 KB Output is correct
12 Correct 2242 ms 12348 KB Output is correct
13 Correct 2033 ms 12192 KB Output is correct
14 Correct 649 ms 9992 KB Output is correct
15 Correct 1061 ms 10484 KB Output is correct
16 Correct 3318 ms 12680 KB Output is correct
17 Correct 4219 ms 14240 KB Output is correct
18 Correct 4080 ms 14288 KB Output is correct
19 Correct 2708 ms 13928 KB Output is correct
20 Correct 3988 ms 14160 KB Output is correct
21 Correct 3892 ms 14420 KB Output is correct
22 Correct 3092 ms 13924 KB Output is correct
23 Correct 8553 ms 21636 KB Output is correct
24 Execution timed out 9079 ms 21724 KB Time limit exceeded
25 Halted 0 ms 0 KB -