Submission #28540

# Submission time Handle Problem Language Result Execution time Memory
28540 2017-07-16T07:08:54 Z AcornCkiGuiziTeam(#1202, dotorya, cki86201, zigui) 1-Color Coloring (FXCUP2_coloring) C++11
1 / 1
0 ms 2024 KB
#include "coloring.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

vector<int> v;
int cc;
int dd;

void myColor(int x) {
    ++cc;
    Color(x);
}

int get(vector <int> v, int p) {
    if(sz(v) == 1) return v[0];
    int L = sz(v);
    rep(i, L/2) myColor(v[i]);
    int t = GetColor(p); ++dd;
    if(t == 1) {
        vector <int> temp;
        for(int i=L/2;i<L;i++) temp.pb(v[i]);
        return get(temp, p);
    }
    else {
        vector <int> temp;
        for(int i=0;i<L/2;i++) temp.pb(v[i]);
        return get(temp, p);
    }
}

void ColoringSame(int N){
    for(int i=2;i<=N;i++) v.pb(i);
    random_shuffle(all(v));    
    int p = 1;
    vector <int> X;
    
    for(int i=1;;i++) {
//	printf("%d %d %d\n", i, cc, dd);
        int t = get(v, p);
        X.pb(t);
        p = t;
        for(int a=0;a<sz(v);a++) if(v[a] == t) {
            swap(v[a], v.back());
            v.pop_back();
            break;
        }
        int L = N - i - 1;
        if(cc + L * (L - 1) + N <= 7300) break;
    }
    Color(1);
    int L = sz(v);
    rep(i, L) rep(j, L) Color(v[j]);
    reverse(all(X));
    for(int e : X) Color(e);
    
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct
13 Correct 0 ms 2024 KB Output is correct
14 Correct 0 ms 2024 KB Output is correct
15 Correct 0 ms 2024 KB Output is correct
16 Correct 0 ms 2024 KB Output is correct
17 Correct 0 ms 2024 KB Output is correct
18 Correct 0 ms 2024 KB Output is correct
19 Correct 0 ms 2024 KB Output is correct
20 Correct 0 ms 2024 KB Output is correct
21 Correct 0 ms 2024 KB Output is correct
22 Correct 0 ms 2024 KB Output is correct
23 Correct 0 ms 2024 KB Output is correct
24 Correct 0 ms 2024 KB Output is correct
25 Correct 0 ms 2024 KB Output is correct