oj.uz

답안 #739421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739421 2023-05-10T12:34:21 Z onebit1024 Data Transfer (IOI19_transfer) C++17
60 / 100
 3000 ms 2448 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
1 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;

	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;
	}
	for(int i = 0;i<N;++i){
 
		int nsum = 0;
		data[i] = 1-data[i];
		v = 3;
		for(int j = 0;j<N;++j){
			while(power(v))v++;

			if(data[j])nsum^=v;
			v++;
		}
		data[i] = 1-data[i];
		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:72:6: warning: unused variable 'bits' [-Wunused-variable]
   72 |  int bits = data.size()-N;
      |      ^~~~

Subtask #1
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 704 KB Output is correct
2 Correct 26 ms 648 KB Output is correct
3 Correct 24 ms 780 KB Output is correct
4 Correct 26 ms 696 KB Output is correct
5 Correct 26 ms 644 KB Output is correct
6 Correct 27 ms 648 KB Output is correct
7 Correct 30 ms 788 KB Output is correct
8 Correct 24 ms 740 KB Output is correct
9 Correct 24 ms 640 KB Output is correct
10 Correct 24 ms 728 KB Output is correct
11 Correct 26 ms 700 KB Output is correct
12 Correct 26 ms 664 KB Output is correct
13 Correct 29 ms 644 KB Output is correct
14 Correct 27 ms 756 KB Output is correct
15 Correct 27 ms 804 KB Output is correct
16 Correct 25 ms 652 KB Output is correct
17 Correct 35 ms 840 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3069 ms 2448 KB Time limit exceeded
2 Halted 0 ms 0 KB -