oj.uz

Submission #255231

# Submission time Handle Problem Language Result Execution time Memory
255231 2020-07-31T15:30:13 Z Abelyan Mechanical Doll (IOI18_doll) C++17
100 / 100
 134 ms 14744 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

//#pragma GCC target("avx2")
//#pragma GCC optimization("unroll-loops")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=2e6+6;

struct ban{
	int key;
	int* a;
	ban(){}
	ban(int _key,int* _a){
		key=_key;
		a=_a;
	}
	bool operator < (ban other){
		if (key<other.key)return true;
		return false;
	}
};

int n,qan=1,tv=0;
int x[N],y[N];
vector<int> c;
vector<ban> vc;

int cnt=0;
int pw=1,ham=0;

void build(int l,int r,int *pr){
	int sz=(r-l+1);
	
	
	if (sz<=tv){
		tv-=sz;
		*pr=-1;
		return;
	}
	if (l==r){
		//cout<<<endl;
		vc.ad({ham,pr});
		return;
	}
	int md=(l+r)/2;
	int tham=cnt++;
	pw*=2;
	//cout<<l<<" "<<md<<" "<<&x[tham]<<endl;
	build(l,md,&x[tham]);
	ham+=(pw/2);
	build(md+1,r,&y[tham]);
	ham-=(pw/2);
	pw/=2;
	*pr=-(tham+1);
	//cout<<tham+1<<" "<<x[tham]<<" "<<y[tham]<<endl;

}

void create_circuit(int m, vector<int> a) {
	n=a.size();
	c.resize(m+1,-1);
	int nn=n;
	while(nn!=1){
		nn/=2;
		qan++;
	}
	qan=(1<<qan);
	n++;
	tv=qan-n;
	//cout<<tv<<endl;
	int smth;
	build(0,qan-1,&smth);
	sort(all(vc));
	//cout<<1<<endl;
	vector<int> xx,yy;
	
	FOR(i,vc.size()){
		if (i==vc.size()-1)*vc[i].a=0;
		else *vc[i].a=a[i];
	}
	//cout<<vc.size()<<endl;
	//cout<<"--"<<" "<<cnt<<endl;
	FOR(i,cnt){
		//cout<<x[i]<<" "<<y[i]<<endl;
		xx.ad(x[i]);
		yy.ad(y[i]);
	}
	//cout<<2<<endl;
	answer(c,xx,yy);
	
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:14:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i,a) for (int i=0;i<(a);++i)
      |                                ^
doll.cpp:100:2: note: in expansion of macro 'FOR'
  100 |  FOR(i,vc.size()){
      |  ^~~
doll.cpp:101:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if (i==vc.size()-1)*vc[i].a=0;
      |       ~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 6256 KB Output is correct
3 Correct 38 ms 5736 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 62 ms 8624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 6256 KB Output is correct
3 Correct 38 ms 5736 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 62 ms 8624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 71 ms 9676 KB Output is correct
9 Correct 91 ms 10408 KB Output is correct
10 Correct 120 ms 14744 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 6256 KB Output is correct
3 Correct 38 ms 5736 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 62 ms 8624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 71 ms 9676 KB Output is correct
9 Correct 91 ms 10408 KB Output is correct
10 Correct 120 ms 14744 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 112 ms 14228 KB Output is correct
15 Correct 67 ms 9164 KB Output is correct
16 Correct 112 ms 14088 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 113 ms 14560 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 8516 KB Output is correct
3 Correct 62 ms 8488 KB Output is correct
4 Correct 134 ms 12956 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 8516 KB Output is correct
3 Correct 62 ms 8488 KB Output is correct
4 Correct 134 ms 12956 KB Output is correct
5 Correct 105 ms 13892 KB Output is correct
6 Correct 106 ms 13812 KB Output is correct
7 Correct 118 ms 13844 KB Output is correct
8 Correct 100 ms 13624 KB Output is correct
9 Correct 62 ms 8508 KB Output is correct
10 Correct 99 ms 13568 KB Output is correct
11 Correct 115 ms 13348 KB Output is correct
12 Correct 62 ms 8744 KB Output is correct
13 Correct 69 ms 8992 KB Output is correct
14 Correct 67 ms 9124 KB Output is correct
15 Correct 83 ms 9112 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 59 ms 8788 KB Output is correct
18 Correct 60 ms 8744 KB Output is correct
19 Correct 71 ms 8760 KB Output is correct
20 Correct 97 ms 13504 KB Output is correct
21 Correct 98 ms 13236 KB Output is correct
22 Correct 100 ms 13336 KB Output is correct