CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:socho
Submission time:2021-01-30 20:05:13 +0200
Language:C++17
Status:READY
Result:7
Feedback
groupverdictscore
#1ACCEPTED7
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 4, 5details
#2ACCEPTED0.01 s1, 2, 4, 5details
#3ACCEPTED0.01 s1, 2, 4, 5details
#4ACCEPTED0.01 s1, 2, 4, 5details
#5ACCEPTED0.01 s1, 2, 4, 5details
#6--2, 4, 5details
#7--2, 4, 5details
#8--2, 4, 5details
#9--2, 4, 5details
#10--2, 4, 5details
#110.01 s4, 5details
#120.01 s5details
#130.01 s3, 4, 5details
#140.01 s3, 4, 5details
#15ACCEPTED0.01 s1, 2, 4, 5details
#160.01 s4, 5details
#170.01 s4, 5details
#180.01 s5details
#19ACCEPTED0.01 s1, 2, 4, 5details
#20--2, 4, 5details
#21--2, 4, 5details
#22--2, 4, 5details
#230.01 s4, 5details
#240.01 s4, 5details
#250.01 s4, 5details
#260.01 s5details
#270.01 s5details
#280.01 s5details
#290.01 s5details
#30ACCEPTED0.01 s1, 2, 4, 5details

Compiler report

input/code.cpp: In function 'void test(std::vector<int>)':
input/code.cpp:120:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) {
                ~^~~~~~~~~
input/code.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=i+1; j<v.size(); j++) {
                   ~^~~~~~~~~
input/code.cpp:131:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<h.size(); j++) {
                 ~^~~~~~~~~
input/code.cpp: In function 'void usaco()':
input/code.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("problem.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused

Code

#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
// #define endl '\n'
// #define double long double
// #define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;

const int MXN = 15;
int n;
int p[MXN];
int pos[MXN];
string s;

struct hline {
	int lx, rx, aty;
	int rl;
	hline(int a, int b, int c, int id) {
		if (a > b) swap(a, b);
		lx = a;
		rx = b;
		aty = c;
		rl = id;
	}
};

struct vline {
	int ty, by, atx;
	int rl;
	vline(int a, int b, int c, int id) {
		if (a < b) swap(a, b);
		ty = a;
		by = b;
		atx = c;
		rl = id;
	}
};

bool intersect(vline a, hline b) {
	
	if (abs(a.rl - b.rl) == 1) return false;
	
	if (b.aty > a.ty || b.aty < a.by) return false;
	if (a.atx < b.lx || a.atx > b.rx) return false;
	return true;
	
}

bool intersect(vline a, vline b) {
	
	if (abs(a.rl - b.rl) == 1) return false;
	
	if (a.atx != b.atx) return false;
	if (a.ty < b.by) return false;
	if (a.by > b.ty) return false;
	return true;
	
}

void test(vector<int> order) {
	
	for (int i=0; i<n; i++) {
		pos[order[i]] = i;
	}
	
	for (int i=1; i<n; i++) {
		if (pos[i] < pos[i-1]) {
			if (s[i-1] == 'U') return;
		}
		else {
			if (s[i-1] == 'D') return;
		}
	}
	
	vector<int> trl;
	for (int i=1; i<n; i++) {
		trl.push_back(pos[i] - pos[i-1]);
	}
	
	vector<hline> h;
	vector<vline> v;
	
	int tx = 0;
	
	int x=0, y=0;
	for (int i=0; i<n-1; i++) {
		// cout << x << ' ' << y << endl;
		// cout << " > to: ";
		h.push_back(hline(x, x+p[i], y, tx));
		tx++;
		x += p[i];
		// cout << x << ' ' << y << endl;
		// cout << " > to: ";
		v.push_back(vline(y, y+trl[i], x, tx));
		tx++;
		y += trl[i];
		// cout << x << ' ' << y << endl;
	}
	h.push_back(hline(x, x+p[n-1], y, tx));
	
	// cout << "n" << endl;
	
	for (int i=0; i<v.size(); i++) {
		for (int j=i+1; j<v.size(); j++) {
			if (intersect(v[i], v[j])) {
				
				// cout << "IN: " << endl;
				// cout << v[i].atx << ' ' << v[i].by << " to " << v[i].atx << ' ' << v[i].ty << endl;
				// cout << v[j].atx << ' ' << v[j].by << " to " << v[j].atx << ' ' << v[j].ty << endl;
				
				return;
			}
		}
		for (int j=0; j<h.size(); j++) {
			if (intersect(v[i], h[j])) {
				
				// cout << "IN: " << endl;
				// cout << v[i].atx << ' ' << v[i].by << " to " << v[i].atx << ' ' << v[i].ty << endl;
				// cout << h[j].lx << ' ' << h[j].aty << " to " << h[j].rx << ' ' << h[j].aty << endl;
				
				return;
			}
		}
	}
	
	cout << "YES" << endl;
	for (int i=1; i<n; i++) {
		cout << abs(pos[i] - pos[i-1]) << ' ';
	}
	cout << endl;
	exit(0);
	
}

signed main() {

	ran(); fast();

	cin >> n;
	for (int i=0; i<n; i++) {
		cin >> p[i];
		if (i % 2 == 1) p[i] = -p[i];
	}
	cin >> s;
	
	vector<int> t;
	for (int i=0; i<n; i++) t.push_back(i);
	
	do {
		
		test(t);
		
	} while (next_permutation(t.begin(), t.end()));
	
	cout << "NO" << endl;

}

Test details

Test 1

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
2
2 10
D

correct output
YES

user output
YES

Test 2

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
5 8 7 5 6 5 3 4
DUUUDDD

correct output
YES
1 5 1 1 3 1 1 

user output
YES
1 5 1 1 3 1 1 

Test 3

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
9 8 8 10 10 8 9 10
DDDUUUD

correct output
YES
1 1 1 4 1 1 7 

user output
YES
1 1 1 5 1 1 3 

Test 4

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
9 10 8 8 9 9 7 8
DDDDUUU

correct output
NO

user output
NO

Test 5

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
10 2 8 3 10 2 10 10
DDUUUUD

correct output
YES
1 1 3 1 1 1 7 

user output
YES
1 1 3 2 1 1 3 

Test 6

Group: 2, 4, 5

Verdict:

input
15
73 74 97 82 19 50 26 51 56 93 ...

correct output
YES
1 2 3 1 1 3 1 1 1 10 1 3 1 1 

user output
(empty)

Test 7

Group: 2, 4, 5

Verdict:

input
15
95 71 97 77 98 76 100 62 96 69...

correct output
YES
1 1 3 1 1 1 1 1 9 1 11 1 13 1 

user output
(empty)

Test 8

Group: 2, 4, 5

Verdict:

input
15
79 81 84 86 88 90 92 92 91 89 ...

correct output
YES
1 2 3 4 5 6 14 1 6 5 4 3 2 1 

user output
(empty)

Test 9

Group: 2, 4, 5

Verdict:

input
15
97 90 87 83 79 76 74 23 24 76 ...

correct output
YES
13 11 9 7 5 3 1 1 3 5 7 9 11 1...

user output
(empty)

Test 10

Group: 2, 4, 5

Verdict:

input
15
100 2 99 1 78 4 93 2 100 1 15 ...

correct output
NO

user output
(empty)

Test 11

Group: 4, 5

Verdict:

input
1000
999997 999995 999993 999991 99...

correct output
YES
997 995 993 991 989 987 985 98...

user output
(empty)

Test 12

Group: 5

Verdict:

input
100000
999999998 999999996 999999994 ...

correct output
YES
99997 99995 99993 99991 99989 ...

user output
(empty)

Test 13

Group: 3, 4, 5

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
YES

Test 14

Group: 3, 4, 5

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
NO

user output
YES

Test 15

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
5
6 7 7 6 6
UDUU

correct output
YES
1 4 1 1 

user output
YES
1 4 1 1 

Test 16

Group: 4, 5

Verdict:

input
30
15 12 9 88 10 26 78 23 67 14 9...

correct output
YES
1 1 1 4 1 3 1 1 7 1 19 1 1 3 1...

user output
YES

Test 17

Group: 4, 5

Verdict:

input
1000
1000000 1 146324 146324 289287...

correct output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
(empty)

Test 18

Group: 5

Verdict:

input
100000
1000000000 1 421262579 4212625...

correct output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
(empty)

Test 19

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
1 3 1 2 5 1 1 2
DUUUDUU

correct output
NO

user output
NO

Test 20

Group: 2, 4, 5

Verdict:

input
15
3 1 33 13 1 11 32 8 1 19 15 25...

correct output
YES
1 1 5 1 1 3 5 1 1 1 1 5 2 1 

user output
(empty)

Test 21

Group: 2, 4, 5

Verdict:

input
15
10 2 39 41 42 34 31 28 26 24 2...

correct output
YES
1 1 1 1 10 9 8 7 6 1 4 1 1 1 

user output
(empty)

Test 22

Group: 2, 4, 5

Verdict:

input
15
27 4 6 23 26 37 40 38 44 27 3 ...

correct output
YES
1 1 1 1 5 1 7 1 3 1 1 3 1 1 

user output
(empty)

Test 23

Group: 4, 5

Verdict:

input
1000
3246 3562 197273 197429 197755...

correct output
YES
1 1 1 4 5 10 3 1 1 3 7 12 1 1 ...

user output
(empty)

Test 24

Group: 4, 5

Verdict:

input
1000
503981 503487 503350 502673 50...

correct output
YES
999 1 997 1 1 994 989 1 1 1 1 ...

user output
(empty)

Test 25

Group: 4, 5

Verdict:

input
1000
1445 1363 1749 1084 262408 263...

correct output
NO

user output
(empty)

Test 26

Group: 5

Verdict:

input
100000
209655 9167 9389 191291 198294...

correct output
NO

user output
(empty)

Test 27

Group: 5

Verdict:

input
100000
16295 14904 5103 13337 26939 3...

correct output
YES
1 1 1 1 5 6 1 1 1 10 11 1 13 1...

user output
(empty)

Test 28

Group: 5

Verdict:

input
100000
1859 174288 15040 4631 4993844...

correct output
YES
1 3 1 1 99997 99992 1 1 5 1 1 ...

user output
(empty)

Test 29

Group: 5

Verdict:

input
100000
959817 958289 966165 922369 92...

correct output
YES
1 1 1 1 1 1 1 1 1 1 11 14 1 1 ...

user output
(empty)

Test 30

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
2 3 2 3 5 6 7 8
UDDDUDU

correct output
YES
1 2 1 1 5 6 7 

user output
YES
3 1 1 2 5 6 7