oj.uz

답안 #830091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830091 2023-08-18T18:44:47 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 1785 ms 12888 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define all(x) (x).begin(), (x).end()

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vii = vector<pii>;
void nadaj(vi &V, int x, int b){
	for(int i=0; i<b; i++){
		V.pb(!!(x&(1<<i)));
	}
}
void encode2(vi &ans, int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	bool spec[n];
	queue<int> spe;
	for(int v=0; v<n; v++){
		int ile=0;
		vii V2;
		for(int u=0; u<n; u++){
			if(u==v)continue;
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			b=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					V2.eb(u, i);
					b=1;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					V2.eb(v, i);
					b=1;
				}
			}
			if(b)ile++;
		}
		sort(all(V2));
		V2.resize(unique(all(V2))-V2.begin());
		if(ile>=111){
			spe.push(v);
			spec[v]=1;
			for(int u=0; u<n; u++){
				if(u==v)continue;
				bool b=1;
				for(int i=0; i<h; i++){
					if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
						b=0;
					}
				}
				if(!b)continue;
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
						E2[v].pb(u);
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
						E2[v].pb(u);
					}
				}
			}
		}
	}
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				if(2*(u-v)<=n)E2[v].pb(u);
				else E2[u].pb(v);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	while(spe.size()){
		int v=spe.front();
		spe.pop();
		if(E2[v].size()>=111)continue;
		vi V;
		spec[v]=0;
		for(int u:E2[v]){
			if(2*(u-v)<=n)V.pb(u);
			else{
				E2[u].pb(v);
				if(E2[u].size()==111){
					spec[u]=1;
					spe.push(u);
				}
			}
		}
		E2[v]=V;
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		if(spec[i]){
			assert(E2[i].size()>=111);
			nadaj(ans, 111, 7);
		}
		else{
			assert(E2[i].size()<100);
			nadaj(ans, E2[i].size(), 7);
		}
		//assert(spec[i]==(E2[i].size()>=111));
		if(spec[i]){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(ans, j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(ans, (u-i+n)%n, 9);
			}
		}
	}
	return;
}
void encode3(vi &ans, int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				if(2*(u-v)<=n)E2[v].pb(u);
				else E2[u].pb(v);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		nadaj(ans, min((int)E2[i].size(), 111), 7);
		if(E2[i].size()>=111){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(ans, j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(ans, (u-i+n)%n, 9);
			}
		}
	}
	return;
}
void encode(int n, int h, int m, int *v1, int *v2){
	vi V, V2;
	encode2(V, n, h, m, v1, v2);
	//encode3(V2, n, h, m, v1, v2);
	//if(V2.size()<V.size())V=V2;
	for(int i:V){
		encode_bit(i);
	}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
int czytaj(int b){
	int x=0;
	for(int i=0; i<b; i++){
		x+=(int(decode_bit())<<i);
	}
	return x;
}
void decode(int n, int h) {
	vi E[n];
	for(int i=0;i<n; i++){
		int k=czytaj(7);
		//cerr<<k<<"\n";
		if(k>=111){
			for(int j=0; j<n; j++){
				if(czytaj(1)){
					E[i].pb(j);
					E[j].pb(i);
				}
			}
		}
		else{
			while(k--){
				int j=czytaj(9);
				E[i].pb((j+i)%n);
				E[(j+i)%n].pb(i);
			}
		}
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		vi dist(n, 1e9);
		dist[s]=0;
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int u:E[v]){
				if(dist[u]==1e9){
					dist[u]=dist[v]+1;
					V.pb(u);
				}
			}
		}
		for(int i=0; i<n; i++){
			hops(s, i, dist[i]);
		}
	}
}

Compilation message

encoder.cpp: In function 'void encode2(vi&, int, int, int, int*, int*)':
encoder.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:207:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1634 ms 12888 KB Output is correct - 43000 call(s) of encode_bit()
2 Runtime error 2 ms 464 KB Execution killed with signal 6
3 Correct 849 ms 5844 KB Output is correct - 40689 call(s) of encode_bit()
4 Runtime error 2 ms 464 KB Execution killed with signal 6
5 Incorrect 980 ms 6632 KB Output isn't correct
6 Incorrect 1170 ms 6824 KB Output isn't correct
7 Incorrect 1689 ms 7136 KB Output isn't correct
8 Correct 1555 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 841 ms 5488 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 859 ms 5492 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 930 ms 6040 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1099 ms 5332 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1708 ms 7116 KB Output isn't correct
14 Correct 1071 ms 5576 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1045 ms 5620 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1201 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1172 ms 6312 KB Output isn't correct
18 Incorrect 1331 ms 6876 KB Output isn't correct
19 Incorrect 1430 ms 6304 KB Output isn't correct
20 Correct 1214 ms 7364 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1372 ms 7728 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1785 ms 7080 KB Output isn't correct
23 Correct 1365 ms 7960 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1634 ms 12888 KB Output is correct - 43000 call(s) of encode_bit()
2 Runtime error 2 ms 464 KB Execution killed with signal 6
3 Correct 849 ms 5844 KB Output is correct - 40689 call(s) of encode_bit()
4 Runtime error 2 ms 464 KB Execution killed with signal 6
5 Incorrect 980 ms 6632 KB Output isn't correct
6 Incorrect 1170 ms 6824 KB Output isn't correct
7 Incorrect 1689 ms 7136 KB Output isn't correct
8 Correct 1555 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 841 ms 5488 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 859 ms 5492 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 930 ms 6040 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1099 ms 5332 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1708 ms 7116 KB Output isn't correct
14 Correct 1071 ms 5576 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1045 ms 5620 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1201 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1172 ms 6312 KB Output isn't correct
18 Incorrect 1331 ms 6876 KB Output isn't correct
19 Incorrect 1430 ms 6304 KB Output isn't correct
20 Correct 1214 ms 7364 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1372 ms 7728 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1785 ms 7080 KB Output isn't correct
23 Correct 1365 ms 7960 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1634 ms 12888 KB Output is correct - 43000 call(s) of encode_bit()
2 Runtime error 2 ms 464 KB Execution killed with signal 6
3 Correct 849 ms 5844 KB Output is correct - 40689 call(s) of encode_bit()
4 Runtime error 2 ms 464 KB Execution killed with signal 6
5 Incorrect 980 ms 6632 KB Output isn't correct
6 Incorrect 1170 ms 6824 KB Output isn't correct
7 Incorrect 1689 ms 7136 KB Output isn't correct
8 Correct 1555 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 841 ms 5488 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 859 ms 5492 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 930 ms 6040 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1099 ms 5332 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1708 ms 7116 KB Output isn't correct
14 Correct 1071 ms 5576 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1045 ms 5620 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1201 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1172 ms 6312 KB Output isn't correct
18 Incorrect 1331 ms 6876 KB Output isn't correct
19 Incorrect 1430 ms 6304 KB Output isn't correct
20 Correct 1214 ms 7364 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1372 ms 7728 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1785 ms 7080 KB Output isn't correct
23 Correct 1365 ms 7960 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1634 ms 12888 KB Output is correct - 43000 call(s) of encode_bit()
2 Runtime error 2 ms 464 KB Execution killed with signal 6
3 Correct 849 ms 5844 KB Output is correct - 40689 call(s) of encode_bit()
4 Runtime error 2 ms 464 KB Execution killed with signal 6
5 Incorrect 980 ms 6632 KB Output isn't correct
6 Incorrect 1170 ms 6824 KB Output isn't correct
7 Incorrect 1689 ms 7136 KB Output isn't correct
8 Correct 1555 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 841 ms 5488 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 859 ms 5492 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 930 ms 6040 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1099 ms 5332 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1708 ms 7116 KB Output isn't correct
14 Correct 1071 ms 5576 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1045 ms 5620 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1201 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1172 ms 6312 KB Output isn't correct
18 Incorrect 1331 ms 6876 KB Output isn't correct
19 Incorrect 1430 ms 6304 KB Output isn't correct
20 Correct 1214 ms 7364 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1372 ms 7728 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1785 ms 7080 KB Output isn't correct
23 Correct 1365 ms 7960 KB Output is correct - 60188 call(s) of encode_bit()