| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 173871 |
2020-01-05T16:32:35 Z |
Ruxandra985 |
ICC (CEOI16_icc) |
C++14 |
|
149 ms |
688 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int f[110] , w[110] , a[110] , b[110] , idk[110] , b2[110] , a2[110] , nope[110];
int ca[110] , cb[110] , logg[110];
void run (int n){
int i , p , q , bit , en , elem , j , p2 , q2 , ea , eb , k;
logg[0] = -1;
for (i=1;i<=n;i++){
f[i] = i;
logg[i] = 1 + logg[i/2];
}
for (int mc = 1 ; mc < n ; mc++){
//if (mc == 4)
// printf ("a");
/// vreau sa ma duc in jos cat pot pana gasesc intervalul care contine capetele
bit = 0;
en = elem = 0;
while (bit <= logg[n - mc + 1]){
p = q = 0;
for (i=1;i<=n;i++){
if (f[i] & (1 << bit))
a[p++] = i;
}
for (i=1;i<=n;i++){
if ((f[i] & (1 << bit)) == 0)
b[q++] = i;
}
if (query( p , q , a , b ) == 1){
/// un capat de muchie e intr o jumatate , celalalt capat in cealalta
idk[++elem] = bit; /// bitul bit e diferit in comp(x) si comp(y)
}
else nope[++en] = bit; /// sunt la fel
bit++;
}
memset (a , 0 , sizeof(a));
memset (a2 , 0 , sizeof(a2));
memset (b , 0 , sizeof(b));
memset (b2 , 0 , sizeof(b2));
//if (mc == 4)
// printf ("a");
p = q = n - mc + 1;
for (i=0;i<n - mc + 1;i++){
a[i] = b[i] = i + 1;
}
for (i = 1 ; i <= elem ; i++){
for (j=0;j<p;j++){
a2[j] = a[j];
}
for (j=0;j<q;j++){
b2[j] = b[j];
}
p2 = p;
q2 = q;
/// in a le punem pe alea cu 1 , in b pe alea cu 0
for (j = 0 ; j < p2 ; j++){
if ( (a2[j] & (1 << idk[i])) ==0 ){ /// asta are 0 , nu e ok
swap(a2[p2 - 1] , a2[j]);
p2--;
j--;
}
}
for (j = 0 ; j < q2 ; j++){
if ( (b2[j] & (1 << idk[i])) != 0 ){ /// asta are 1 , nu e ok
swap(b2[q2 - 1] , b2[j]);
q2--;
j--;
}
}
/// in a2 ti au ramas cele cu configuratie fixata + 1
/// in b2 ti au ramas cu configuratie fixata + 0
/// inainte de query trebuie sa faci un convert
ea = eb = 0;
for (j=0;j<p2;j++){
for (k=1;k<=n;k++){
if (f[k] == a2[j])
ca[ea++] = k;
}
}
for (j=0;j<q2;j++){
for (k=1;k<=n;k++){
if (f[k] == b2[j])
cb[eb++] = k;
}
}
if (i != 1 && query( ea , eb , ca , cb ) == 0){ /// ai pierdut
for (j=0;j<p;j++){
a2[j] = a[j];
}
for (j=0;j<q;j++){
b2[j] = b[j];
}
p2 = p;
q2 = q;
/// in a le punem pe alea cu 0 , in b pe alea cu 1
for (j = 0 ; j < p2 ; j++){
if ( (a2[j] & (1 << idk[i])) != 0 ){ /// asta are 1 , nu e ok
swap(a2[p2 - 1] , a2[j]);
p2--;
j--;
}
}
for (j = 0 ; j < q2 ; j++){
if ( (b2[j] & (1 << idk[i])) == 0 ){ /// asta are 0 , nu e ok
swap(b2[q2 - 1] , b2[j]);
q2--;
j--;
}
}
/// ai inversat ce era de inversat
}
/// e ok
for (j=0;j<p2;j++){
a[j] = a2[j];
}
for (j=0;j<q2;j++){
b[j] = b2[j];
}
p = p2;
q = q2;
}
/// in a si in b ai candidati la solutie
/// cel putin partile cu biti diferiti
/// in felul asta, eviti sa nu ai seturi disjuncte
/// a si b sunt 2 multimi care au intersectia vida
for (i = 1 ; i <= en ; i++){
for (j=0;j<p;j++){
a2[j] = a[j];
}
for (j=0;j<q;j++){
b2[j] = b[j];
}
p2 = p;
q2 = q;
/// in a le punem pe alea cu 1 , in b pe alea cu 0
for (j = 0 ; j < p2 ; j++){
if ( (a2[j] & (1 << nope[i])) == 0 ){ /// asta are 0 , nu e ok
swap(a2[p2 - 1] , a2[j]);
p2--;
j--;
}
}
for (j = 0 ; j < q2 ; j++){
if ( (b2[j] & (1 << nope[i])) == 0 ){ /// asta are 0 , nu e ok
swap(b2[q2 - 1] , b2[j]);
q2--;
j--;
}
}
/// in a2 ti au ramas cele cu configuratie fixata + 0
/// in b2 ti au ramas cu configuratie fixata + 0
ea = eb = 0;
for (j=0;j<p2;j++){
for (k=1;k<=n;k++){
if (f[k] == a2[j])
ca[ea++] = k;
}
}
for (j=0;j<q2;j++){
for (k=1;k<=n;k++){
if (f[k] == b2[j])
cb[eb++] = k;
}
}
if (query( ea , eb , ca , cb ) == 0){ /// ai pierdut
for (j=0;j<p;j++){
a2[j] = a[j];
}
for (j=0;j<q;j++){
b2[j] = b[j];
}
p2 = p;
q2 = q;
/// in a le punem pe alea cu 0 , in b pe alea cu 1
for (j = 0 ; j < p2 ; j++){
if ( (a2[j] & (1 << nope[i])) != 0 ){ /// asta are 1 , nu e ok
swap(a2[p2 - 1] , a2[j]);
p2--;
j--;
}
}
for (j = 0 ; j < q2 ; j++){
if ( (b2[j] & (1 << nope[i])) != 0 ){ /// asta are 1 , nu e ok
swap(b2[q2 - 1] , b2[j]);
q2--;
j--;
}
}
/// ai inversat ce era de inversat
}
/// e ok
for (j=0;j<p2;j++){
a[j] = a2[j];
}
for (j=0;j<q2;j++){
b[j] = b2[j];
}
p = p2;
q = q2;
}
/// ai vectorii a si b
/// a are p elem si b are q
/// a si b sunt indexate de la 0
/// pt a
ea = eb = 0;
for (j=0;j<p;j++){
for (k=1;k<=n;k++){
if (f[k] == a[j])
ca[ea++] = k;
}
}
for (j=0;j<q;j++){
for (k=1;k<=n;k++){
if (f[k] == b[j])
cb[eb++] = k;
}
}
p = ea;
q = eb;
for (i=0;i<p;i++)
a[i] = ca[i];
for (i=0;i<q;i++)
b[i] = cb[i];
while (p > 1){
if (query (p / 2 , q , a , b) == 1)
p/=2;
else {
for (i = p/2 ; i < p ; i++)
a[i - p/2] = a[i];
p = p - p / 2;
}
}
/// pt b
while (q > 1){
if (query (p , q / 2 , a , b) == 1)
q/=2;
else {
for (i = q/2 ; i < q ; i++)
b[i - q/2] = b[i];
q = q - q / 2;
}
}
setRoad(a[0] , b[0]);
/// acum trebuie sa modificam f ul
int u1 = min( f[a[0]] , f[b[0]] );
int u2 = max( f[a[0]] , f[b[0]] );
for (i=1;i<=n;i++){
if (f[i] == u2)
f[i] = u1;
else if (f[i] == n - mc + 1 && u2 != n - mc + 1)
f[i] = u2;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 123 queries used. |
| 2 |
Correct |
10 ms |
504 KB |
Ok! 121 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
508 KB |
Ok! 662 queries used. |
| 2 |
Correct |
43 ms |
596 KB |
Ok! 593 queries used. |
| 3 |
Correct |
47 ms |
588 KB |
Ok! 646 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
636 KB |
Ok! 1621 queries used. |
| 2 |
Correct |
136 ms |
504 KB |
Ok! 1524 queries used. |
| 3 |
Correct |
140 ms |
632 KB |
Ok! 1625 queries used. |
| 4 |
Correct |
144 ms |
560 KB |
Ok! 1598 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
504 KB |
Ok! 1616 queries used. |
| 2 |
Correct |
145 ms |
596 KB |
Ok! 1606 queries used. |
| 3 |
Correct |
140 ms |
560 KB |
Ok! 1625 queries used. |
| 4 |
Correct |
147 ms |
556 KB |
Ok! 1622 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
560 KB |
Ok! 1605 queries used. |
| 2 |
Correct |
141 ms |
688 KB |
Ok! 1601 queries used. |
| 3 |
Correct |
142 ms |
632 KB |
Ok! 1601 queries used. |
| 4 |
Correct |
141 ms |
596 KB |
Ok! 1606 queries used. |
| 5 |
Correct |
145 ms |
636 KB |
Ok! 1625 queries used. |
| 6 |
Correct |
146 ms |
504 KB |
Ok! 1619 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
636 KB |
Ok! 1601 queries used. |
| 2 |
Correct |
142 ms |
564 KB |
Ok! 1601 queries used. |
