oj.uz

Submission #716919

# Submission time Handle Problem Language Result Execution time Memory
716919 2023-03-31T11:54:46 Z myrcella Mechanical Doll (IOI18_doll) C++17
100 / 100
 114 ms 15392 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "doll.h"

const int maxn = 4e6+10;

vector <int> X,Y;
int tot;
int cur = 1;
int cnt = 0;

void dfs(int suf,int lg) {
	int id = cur++;
	X.pb(-mod),Y.pb(-mod);
	lg--;
	if (lg==0) {
		if (suf+1==tot) X[id-1] = -1;
		return;
	}
	Y[id-1] = -cur;
	dfs(suf,lg);
	if (suf + (1<<lg) < tot) {
		X[id-1] = -cur;
		dfs(suf + (1<<lg), lg);
	}
	else X[id-1] = -1;
}

bool vis[maxn];

int nxt(int x) {
	int ret;
	if (vis[x]==false) ret = X[x-1];
	else ret = Y[x-1];
	vis[x]^=1;
	if (vis[x]) cnt++;
	else cnt--;
	return -ret;
}

void create_circuit(int M, std::vector<int> A) {
	tot=SZ(A)+1;
  A.pb(0);
  int lg = 0;
  while ((1<<lg)<tot) lg++;
  dfs(0,lg);
  memset(vis,0,sizeof(vis));
  rep(i,0,tot) {
	  int cur=1,tmp;
	  while ((tmp=nxt(cur))!=mod) {
		  cur = tmp;
	  }
		if (vis[cur]==false) Y[cur-1] = A[i];
		else X[cur-1] = A[i];
  }
  vector <int> C;
  rep(i,0,M+1) C.pb(-1);
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 47 ms 7724 KB Output is correct
3 Correct 36 ms 7760 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 11 ms 5452 KB Output is correct
6 Correct 65 ms 9388 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 47 ms 7724 KB Output is correct
3 Correct 36 ms 7760 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 11 ms 5452 KB Output is correct
6 Correct 65 ms 9388 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 71 ms 10624 KB Output is correct
9 Correct 82 ms 11056 KB Output is correct
10 Correct 113 ms 14056 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 47 ms 7724 KB Output is correct
3 Correct 36 ms 7760 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 11 ms 5452 KB Output is correct
6 Correct 65 ms 9388 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 71 ms 10624 KB Output is correct
9 Correct 82 ms 11056 KB Output is correct
10 Correct 113 ms 14056 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct
14 Correct 112 ms 15288 KB Output is correct
15 Correct 68 ms 10960 KB Output is correct
16 Correct 112 ms 14616 KB Output is correct
17 Correct 2 ms 4180 KB Output is correct
18 Correct 2 ms 4148 KB Output is correct
19 Correct 2 ms 4180 KB Output is correct
20 Correct 107 ms 15392 KB Output is correct
21 Correct 2 ms 4180 KB Output is correct
22 Correct 2 ms 4152 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4156 KB Output is correct
2 Correct 62 ms 8984 KB Output is correct
3 Correct 63 ms 8892 KB Output is correct
4 Correct 101 ms 11532 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4156 KB Output is correct
2 Correct 62 ms 8984 KB Output is correct
3 Correct 63 ms 8892 KB Output is correct
4 Correct 101 ms 11532 KB Output is correct
5 Correct 113 ms 14528 KB Output is correct
6 Correct 104 ms 14172 KB Output is correct
7 Correct 100 ms 14140 KB Output is correct
8 Correct 108 ms 13832 KB Output is correct
9 Correct 66 ms 9836 KB Output is correct
10 Correct 98 ms 13752 KB Output is correct
11 Correct 112 ms 13380 KB Output is correct
12 Correct 64 ms 10152 KB Output is correct
13 Correct 68 ms 10480 KB Output is correct
14 Correct 66 ms 10664 KB Output is correct
15 Correct 68 ms 10796 KB Output is correct
16 Correct 3 ms 4424 KB Output is correct
17 Correct 63 ms 10412 KB Output is correct
18 Correct 81 ms 10068 KB Output is correct
19 Correct 79 ms 10328 KB Output is correct
20 Correct 99 ms 13636 KB Output is correct
21 Correct 114 ms 13336 KB Output is correct
22 Correct 100 ms 13376 KB Output is correct