oj.uz

Submission #739290

# Submission time Handle Problem Language Result Execution time Memory
739290 2023-05-10T09:55:55 Z onebit1024 Data Transfer (IOI19_transfer) C++17
80 / 100
 174 ms 2504 KB 
#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back



void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

string bin(int x){
	string res;
	for(int i = 30;i>=0;--i){
		if(x&(1ll<<i))res+='1';
		else res+='0';
	}
	while(!res.empty() && res[0]=='0')res.erase(res.begin());
	return res;
}
int power(int x){
	// is x a power of 2
	while((x%2)==0)x/=2;
	if(x==1)return 1;
	return 0;
}


std::vector<int> get_attachment(std::vector<int> source) {
	int v = 3;
	int x = 0;
	for(int i = 0;i<source.size();++i){
		while(power(v))v++;
		if(source[i])x+=v;
		v++;
	}
	string s= bin(x);
	vector<int>ret;
	for(auto w : s)ret.pb(w-'0');
	return ret;
}
/*
1
2 110101100
*/
std::vector<int> retrieve(std::vector<int> data) {
	int N = 63;
	if(data.size()>100)N = 255;

	int bits = data.size()-N;
	vector<int>ret;
	if(bits==0){
		for(int i = 0;i<data.size();++i)ret.pb(0);
		return ret;
	}
	int v = 3, X = 0, Y = 0;
	for(int i = 0;i<N;++i){
		while(power(v))v++;
		if(data[i])X+=v;
		v++;
	}
	int pos = 0;
	for(int i = data.size()-1;i>=N;--i){
		if(data[i])Y+=(1ll<<pos);
		pos++;
	}
	if(X==Y){
		for(int i = 0;i<N;++i)ret.pb(data[i]);
		return ret;
	}
	v = 3;
	for(int i = 0;i<N;++i){
		while(power(v))v++;

		int nsum = X;
		if(data[i])nsum-=v;
		else nsum+=v;
		if(nsum==Y){
			for(int j = 0;j<i;++j)ret.pb(data[j]);
			ret.pb((data[i]?0:1));
			for(int j = i+1;j<N;++j)ret.pb(data[j]);
			return ret;
		}
		v++;
	}
	for(int i = 0;i<N;++i)ret.pb(data[i]);
	return ret;
}

Compilation message

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0;i<source.size();++i){
      |                ~^~~~~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0;i<data.size();++i)ret.pb(0);
      |                 ~^~~~~~~~~~~~

Subtask #1
48.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 652 KB Output is correct
2 Partially correct 5 ms 636 KB Partially correct
3 Partially correct 5 ms 640 KB Partially correct
4 Partially correct 5 ms 640 KB Partially correct
5 Partially correct 5 ms 736 KB Partially correct
6 Partially correct 6 ms 648 KB Partially correct
7 Partially correct 5 ms 640 KB Partially correct
8 Partially correct 5 ms 648 KB Partially correct
9 Partially correct 5 ms 648 KB Partially correct
10 Partially correct 5 ms 640 KB Partially correct
11 Partially correct 5 ms 640 KB Partially correct
12 Partially correct 4 ms 652 KB Partially correct
13 Partially correct 6 ms 640 KB Partially correct
14 Partially correct 5 ms 640 KB Partially correct
15 Partially correct 6 ms 776 KB Partially correct
16 Partially correct 4 ms 648 KB Partially correct
17 Partially correct 4 ms 732 KB Partially correct

Subtask #2
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 2488 KB Output is correct
2 Correct 158 ms 2488 KB Output is correct
3 Correct 159 ms 2492 KB Output is correct
4 Partially correct 162 ms 2488 KB Partially correct
5 Partially correct 169 ms 2460 KB Partially correct
6 Partially correct 174 ms 2500 KB Partially correct
7 Partially correct 172 ms 2460 KB Partially correct
8 Partially correct 160 ms 2500 KB Partially correct
9 Partially correct 158 ms 2492 KB Partially correct
10 Partially correct 156 ms 2492 KB Partially correct
11 Partially correct 155 ms 2504 KB Partially correct
12 Partially correct 166 ms 2504 KB Partially correct
13 Partially correct 168 ms 2444 KB Partially correct
14 Partially correct 167 ms 2496 KB Partially correct
15 Partially correct 166 ms 2444 KB Partially correct
16 Partially correct 163 ms 2492 KB Partially correct
17 Partially correct 158 ms 2360 KB Partially correct
18 Partially correct 161 ms 2500 KB Partially correct
19 Partially correct 161 ms 2464 KB Partially correct