oj.uz

답안 #830109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830109 2023-08-18T18:59:18 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 1805 ms 12972 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;
					}
				}
			}
			}
		}
	}
	for(int i=0; i<n; i++){
		if(!spec[i]){
			for(int u:E2[i]){
				assert(((u-i+n)%n)<512);
			}
		}
	}
	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;
		
	}
	for(int i=0; i<n; i++){
		if(!spec[i]){
			for(int u:E2[i]){
				//assert(((u-i+n)%n)<512);
			}
		}
	}
	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]){
				//assert((u-i+n)%n<512);
				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:169:12: warning: unused variable 'u' [-Wunused-variable]
  169 |    for(int u:E2[i]){
      |            ^
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:223:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |   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 1668 ms 12972 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 878 ms 5760 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 972 ms 6636 KB Output isn't correct
6 Incorrect 1150 ms 6680 KB Output isn't correct
7 Incorrect 1672 ms 7124 KB Output isn't correct
8 Correct 1321 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 876 ms 5432 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 912 ms 5488 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 988 ms 6000 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1020 ms 5396 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1744 ms 6992 KB Output isn't correct
14 Correct 1073 ms 5440 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1069 ms 5588 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1130 ms 6556 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1124 ms 6376 KB Output isn't correct
18 Incorrect 1261 ms 7000 KB Output isn't correct
19 Incorrect 1439 ms 6424 KB Output isn't correct
20 Correct 1216 ms 7436 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1311 ms 7644 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1805 ms 7076 KB Output isn't correct
23 Correct 1368 ms 8000 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1668 ms 12972 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 878 ms 5760 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 972 ms 6636 KB Output isn't correct
6 Incorrect 1150 ms 6680 KB Output isn't correct
7 Incorrect 1672 ms 7124 KB Output isn't correct
8 Correct 1321 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 876 ms 5432 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 912 ms 5488 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 988 ms 6000 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1020 ms 5396 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1744 ms 6992 KB Output isn't correct
14 Correct 1073 ms 5440 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1069 ms 5588 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1130 ms 6556 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1124 ms 6376 KB Output isn't correct
18 Incorrect 1261 ms 7000 KB Output isn't correct
19 Incorrect 1439 ms 6424 KB Output isn't correct
20 Correct 1216 ms 7436 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1311 ms 7644 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1805 ms 7076 KB Output isn't correct
23 Correct 1368 ms 8000 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1668 ms 12972 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 878 ms 5760 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 972 ms 6636 KB Output isn't correct
6 Incorrect 1150 ms 6680 KB Output isn't correct
7 Incorrect 1672 ms 7124 KB Output isn't correct
8 Correct 1321 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 876 ms 5432 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 912 ms 5488 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 988 ms 6000 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1020 ms 5396 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1744 ms 6992 KB Output isn't correct
14 Correct 1073 ms 5440 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1069 ms 5588 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1130 ms 6556 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1124 ms 6376 KB Output isn't correct
18 Incorrect 1261 ms 7000 KB Output isn't correct
19 Incorrect 1439 ms 6424 KB Output isn't correct
20 Correct 1216 ms 7436 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1311 ms 7644 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1805 ms 7076 KB Output isn't correct
23 Correct 1368 ms 8000 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1668 ms 12972 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 878 ms 5760 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 972 ms 6636 KB Output isn't correct
6 Incorrect 1150 ms 6680 KB Output isn't correct
7 Incorrect 1672 ms 7124 KB Output isn't correct
8 Correct 1321 ms 5412 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 876 ms 5432 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 912 ms 5488 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 988 ms 6000 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1020 ms 5396 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1744 ms 6992 KB Output isn't correct
14 Correct 1073 ms 5440 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1069 ms 5588 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1130 ms 6556 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1124 ms 6376 KB Output isn't correct
18 Incorrect 1261 ms 7000 KB Output isn't correct
19 Incorrect 1439 ms 6424 KB Output isn't correct
20 Correct 1216 ms 7436 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1311 ms 7644 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1805 ms 7076 KB Output isn't correct
23 Correct 1368 ms 8000 KB Output is correct - 60188 call(s) of encode_bit()