oj.uz

Submission #793425

# Submission time Handle Problem Language Result Execution time Memory
793425 2023-07-25T20:12:09 Z Antekb Broken Device (JOI17_broken_device) C++17
0 / 100
 175 ms 2472 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
//#define deb(x...) ;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
#include "Annalib.h"

void Anna( int n, long long X, int K, int P[] ){
	srand(24636346);
	vi kol(n), co(n);
	iota(all(kol), 0);
	random_shuffle(all(kol));
	vi val(n);
	int blo=6;
	int pot=1001;
	for(int i=0; i<n; i++){
		val[i]=rand()%pot;
		co[kol[i]]=i;
	}
	for(int i=0; i<K; i++){
		//deb(kol[P[i]]);
		val[kol[P[i]]]=0;
	}
	vi ans(n);
	for(int i=0; i<blo; i++){
		//deb(i);
		int reszta=X%pot;
		X/=pot;
		vi tim(pot, 1e9);
		tim[0]=-1;
		for(int j=i*n/blo; j<(i+1)*n/blo; j++){
			int t=val[j];
			//deb(t, j);
			for(int k=t; k<pot; k++){
				if(tim[k]==1e9 && tim[k-t]<j)tim[k]=j;
			}
			for(int k=0; k<t; k++){
				if(tim[k]==1e9 && tim[k+pot-t]<j)tim[k]=j;
			}
			if(tim[reszta]!=1e9){
				//deb("a");
				break;
			}
		}
		while(reszta){
			//deb(reszta);
			ans[co[tim[reszta]]]=1;
			int t=val[tim[reszta]];
			//deb(t);
			reszta=(reszta+pot-t)%pot;
		}
	}
	for( int i = 0; i < n; i++ ){
		Set( i, ans[i] );
	}
}

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#include "Brunolib.h"

long long Bruno( int n, int A[] ){
	srand(24636346);
	vi kol(n), co(n);
	iota(all(kol), 0);
	random_shuffle(all(kol));
	vi val(n);
	int blo=6;
	int pot=1001;
	for(int i=0; i<n; i++){
		val[i]=rand()%pot;
		co[kol[i]]=i;
	}
	ll ans=0;
	for(int i=blo-1; i>=0; i--){
		ans*=pot;
		int reszta=0;
		for(int j=i*n/blo; j<(i+1)*n/blo; j++){
			if(A[co[j]]){
				//cerr<<val[j]<<"\n";
				reszta+=val[j];
			}
		}
		ans+=reszta%pot;
	}
	return ans;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 2244 KB Output is correct - L* = 40
2 Correct 160 ms 2264 KB Output is correct - L* = 40
3 Runtime error 12 ms 468 KB Execution killed with signal 11
4 Correct 163 ms 2228 KB Output is correct - L* = 40
5 Runtime error 11 ms 464 KB Execution killed with signal 11
6 Correct 164 ms 2472 KB Output is correct - L* = 40
7 Runtime error 13 ms 464 KB Execution killed with signal 11
8 Runtime error 105 ms 1228 KB Execution killed with signal 11
9 Runtime error 85 ms 1092 KB Execution killed with signal 11
10 Correct 165 ms 2196 KB Output is correct - L* = 40
11 Correct 163 ms 2200 KB Output is correct - L* = 40
12 Runtime error 36 ms 708 KB Execution killed with signal 11
13 Correct 167 ms 2236 KB Output is correct - L* = 40
14 Correct 164 ms 2408 KB Output is correct - L* = 40
15 Runtime error 52 ms 900 KB Execution killed with signal 11
16 Runtime error 159 ms 1592 KB Execution killed with signal 11
17 Correct 171 ms 2240 KB Output is correct - L* = 40
18 Runtime error 104 ms 1312 KB Execution killed with signal 11
19 Correct 165 ms 2224 KB Output is correct - L* = 40
20 Correct 165 ms 2164 KB Output is correct - L* = 40
21 Correct 164 ms 2164 KB Output is correct - L* = 40
22 Correct 168 ms 2288 KB Output is correct - L* = 40
23 Runtime error 12 ms 488 KB Execution killed with signal 11
24 Correct 164 ms 2172 KB Output is correct - L* = 40
25 Runtime error 92 ms 1172 KB Execution killed with signal 11
26 Runtime error 43 ms 632 KB Execution killed with signal 11
27 Runtime error 14 ms 468 KB Execution killed with signal 11
28 Runtime error 56 ms 844 KB Execution killed with signal 11
29 Runtime error 21 ms 504 KB Execution killed with signal 11
30 Correct 161 ms 2228 KB Output is correct - L* = 40
31 Runtime error 54 ms 792 KB Execution killed with signal 11
32 Correct 166 ms 2240 KB Output is correct - L* = 40
33 Runtime error 5 ms 468 KB Execution killed with signal 11
34 Correct 173 ms 2236 KB Output is correct - L* = 40
35 Correct 164 ms 2228 KB Output is correct - L* = 40
36 Correct 168 ms 2252 KB Output is correct - L* = 40
37 Runtime error 59 ms 920 KB Execution killed with signal 11
38 Correct 175 ms 2268 KB Output is correct - L* = 40
39 Correct 164 ms 2176 KB Output is correct - L* = 40
40 Runtime error 1 ms 468 KB Execution killed with signal 11